Data Structures — Binary Search

What is Binary Search?

Binary Search is a divide-and-conquer algorithm that finds the position of a target element in a sorted array.

Instead of checking every element (like Linear Search), it repeatedly divides the search space in half, drastically reducing comparisons.

Get Mandar Deepak Bagwe’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Example

Array: [2, 4, 6, 8, 10, 12, 14, 16]
Target: 10

Step 1 → mid = (0+7)/2 = 3 → arr[3] = 8  < 10 → search right half
Step 2 → mid = (4+7)/2 = 5 → arr[5] = 12 > 10 → search left half
Step 3 → mid = (4+4)/2 = 4 → arr[4] = 10 Found!


Found at index 4 (0-based index).

Java Implementation

A. Iterative Implementation

public class BinarySearch {
    public static int search(int[] arr,int key){
        int low = 0;
        int high = arr.length - 1;

        while(low <= high){
            int mid = low + (high - low) / 2;
            if(arr[mid] == key){
                return mid;
            }
            else if(arr[mid] < key){
                low = mid + 1;
            }
            else if(arr[mid] > key){
                high = mid - 1;
            }
        }

        return -1;
    }
}

Example Run

public class Main {
    public static void main(String[] args) {

        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        int target = 11;
        
        int result = BinarySearch.search(arr, target);
        
        if (result == -1)
            System.out.println("Element not found!");
        else
            System.out.println("Element found at index: " + result);
        
    }
}

Output

Element found at index: 5

B. Recursive Implementation

public class BinarySearch {
    public static int recursiveSearch(int[] arr, int left, int right, int key){
        if(left > right){
            return -1;
        }

        int mid = left + (right - left) / 2;

        if(arr[mid] == key){
            return mid;
        }
        else if(arr[mid] < key){
            return recursiveSearch(arr, mid + 1, right, key);
        }
        else{
            return recursiveSearch(arr, left, mid - 1, key);
        }
    }
}

Example Run

public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8, 10, 12, 14, 16};
        int target = 10;

        int result = BinarySearch.recursiveSearch(arr, 0, arr.length - 1, target);

        if (result == -1)
            System.out.println("Element not found!");
        else
            System.out.println("Element found at index: " + result);

    }
}

Output

Element found at index: 4

Time & Space Complexity

| ------- | -------- | ----------------------------------- |
| Case    | Time     | Space                               |
| ------- | -------- | ----------------------------------- |
| Best    | O(1)     | O(1)                                |
| Average | O(log n) | O(1) iterative / O(log n) recursive |
| Worst   | O(log n) | O(1)                                |
| ------- | -------- | ----------------------------------- |

Comparison with Linear Search

| ---------------- | ------------- | -------------------- |
| Feature          | Linear Search | Binary Search        |
| ---------------- | ------------- | -------------------- |
| Input order      | Unsorted      | Sorted               |
| Time Complexity  | O(n)          | O(log n)             |
| # Comparisons    | n/2 avg       | log₂n                |
| Space Complexity | O(1)          | O(1)                 |
| Practical use    | Small arrays  | Large, sorted arrays |
| ---------------- | ------------- | -------------------- |

Real-Life Applications

• Databases: Searching indexes and records.
• Libraries: Java’s Arrays.binarySearch()
• Operating Systems: Page lookup, memory management.
• Search Engines: Finding word positions in index.
• Games: Level difficulty or score search.
• Auto-suggest systems: Binary search on dictionary prefix arrays.