Binary Search

What is Binary Search?

Binary search is an efficient searching algorithm that works on sorted arrays. It repeatedly divides the search space in half by comparing the target with the middle element, eliminating half the remaining elements with each comparison.

This is a classic Divide and Conquer algorithm. Each step reduces the problem size from n to n/2, giving O(log n) time complexity.

Case	Complexity
Best	O(1) â€” target is the middle element
Average / Worst	O(log n)
Space (iterative)	O(1)
Space (recursive)	O(log n) â€” call stack

Algorithm Steps

Set lo = 0, hi = n - 1
While lo <= hi: compute mid = (lo + hi) / 2
If arr[mid] == target â†’ return mid
If arr[mid] < target â†’ search right half: lo = mid + 1
If arr[mid] > target â†’ search left half: hi = mid - 1
If loop ends without finding â†’ return -1

Binary Search â€” Iterative and Recursive

import java.util.Arrays;

public class BinarySearch {

    // Iterative â€” O(log n) time, O(1) space
    static int binarySearchIter(int[] arr, int target) {
        int lo = 0, hi = arr.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;  // avoids integer overflow
            if (arr[mid] == target) return mid;
            if (arr[mid] < target)  lo = mid + 1;  // search right
            else                    hi = mid - 1;  // search left
        }
        return -1;
    }

    // Recursive â€” O(log n) time, O(log n) space (call stack)
    static int binarySearchRec(int[] arr, int lo, int hi, int target) {
        if (lo > hi) return -1;
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target)  return binarySearchRec(arr, mid + 1, hi, target);
        return binarySearchRec(arr, lo, mid - 1, target);
    }

    // Find first occurrence (for duplicates)
    static int firstOccurrence(int[] arr, int target) {
        int lo = 0, hi = arr.length - 1, result = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] == target) {
                result = mid;
                hi = mid - 1;  // keep searching left
            } else if (arr[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return result;
    }

    // Find last occurrence
    static int lastOccurrence(int[] arr, int target) {
        int lo = 0, hi = arr.length - 1, result = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] == target) {
                result = mid;
                lo = mid + 1;  // keep searching right
            } else if (arr[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        System.out.println("Array: " + Arrays.toString(arr));

        System.out.println("Search 7:  index " + binarySearchIter(arr, 7));   // 3
        System.out.println("Search 15: index " + binarySearchIter(arr, 15));  // 7
        System.out.println("Search 6:  index " + binarySearchIter(arr, 6));   // -1

        int[] dup = {1, 2, 2, 2, 3, 4, 5};
        System.out.println("First 2: index " + firstOccurrence(dup, 2));  // 1
        System.out.println("Last 2:  index " + lastOccurrence(dup, 2));   // 3
    }
}

/*
 * Trace: arr = {1,3,5,7,9,11,13,15,17,19}, target = 7
 * lo=0, hi=9 â†’ mid=4, arr[4]=9 > 7 â†’ hi=3
 * lo=0, hi=3 â†’ mid=1, arr[1]=3 < 7 â†’ lo=2
 * lo=2, hi=3 â†’ mid=2, arr[2]=5 < 7 â†’ lo=3
 * lo=3, hi=3 â†’ mid=3, arr[3]=7 = 7 â†’ return 3
 */

Binary Search Variants

Beyond basic search, binary search can solve many problems:

Variant	Problem	Approach
First occurrence	Find leftmost index of target	When found, continue searching left
Last occurrence	Find rightmost index of target	When found, continue searching right
Count occurrences	How many times does target appear?	lastOccurrence - firstOccurrence + 1
Floor	Largest element ≤ target	Track last element ≤ target
Ceiling	Smallest element ≥ target	Track first element ≥ target
Search in rotated array	Find target in rotated sorted array	Determine which half is sorted
Answer binary search	Find minimum/maximum satisfying a condition	Binary search on the answer space

Binary Search on Answer Space

A powerful technique: instead of searching for a value in an array, binary search on the answer itself. Used when the answer is monotonic â€” if x works, all values > x also work (or vice versa).

Binary Search on Answer â€” Square Root

public class SqrtBinarySearch {

    // Find floor(sqrt(n)) using binary search â€” O(log n)
    static long sqrt(long n) {
        if (n < 2) return n;
        long lo = 1, hi = n / 2, result = 1;
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            if (mid * mid == n) return mid;
            if (mid * mid < n) {
                result = mid;  // mid is a valid floor sqrt
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println("sqrt(16) = " + sqrt(16));   // 4
        System.out.println("sqrt(25) = " + sqrt(25));   // 5
        System.out.println("sqrt(10) = " + sqrt(10));   // 3 (floor)
        System.out.println("sqrt(100) = " + sqrt(100)); // 10
    }
}

Binary Search

What is Binary Search?

Algorithm Steps

Binary Search Variants

Binary Search on Answer Space

Ready to Level Up Your Skills?