Binary Search

Binary search repeatedly cuts a search range in half by checking the middle element and throwing away the half that cannot contain the answer. It turns an O(n) scan into O(log n), so 1,000,000 items need only about 20 checks. Interviewers love it because the idea is simple but the details (boundaries, loop condition, when to stop) are easy to get wrong, and it also hides inside many problems that don't look like a plain search.

When to use it

  • The array (or range of numbers) is sorted, or sorted after a rotation
  • You are asked for O(log n) time, or the input is so large that O(n) feels too slow
  • You need the first or last position of something, or the smallest value that satisfies a condition
  • The answer is a number in a range and you can test 'is this value big enough?' quickly (search on the answer)
  • Words like 'minimum possible maximum' or 'smallest capacity/speed that works' appear in the question

See it work

  1. Find target 23 in the sorted array. Start with the whole array: lo = 0, hi = 6. Compute mid = (0 + 6) / 2 = 3. The value at index 3 is 16. [2, 5, 8, 16, 23, 38, 56]
  2. 16 is smaller than 23, so 23 can only be to the right of index 3. Everything from index 0 to 3 is discarded by moving lo to mid + 1 = 4. [2, 5, 8, 16, 23, 38, 56]
  3. The range is now indices 4 to 6. Compute mid = (4 + 6) / 2 = 5. The value at index 5 is 38. [2, 5, 8, 16, 23, 38, 56]
  4. 38 is bigger than 23, so the answer must be to the left of index 5. Move hi to mid - 1 = 4. The range shrinks to a single cell. [2, 5, 8, 16, 23, 38, 56]
  5. Now lo = hi = 4, so mid = 4. The value at index 4 is 23, which equals the target. Return index 4. We looked at only 3 of the 7 elements. [2, 5, 8, 16, 23, 38, 56]

Code template

Python

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:                 # range still has at least one item
        mid = lo + (hi - lo) // 2   # avoids overflow in other languages
        if nums[mid] == target:
            return mid              # found it
        elif nums[mid] < target:
            lo = mid + 1            # target is in the right half
        else:
            hi = mid - 1            # target is in the left half
    return -1                       # range is empty: not found

# Variant: first index where condition(i) is True (condition flips False -> True)
def first_true(lo, hi, condition):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if condition(mid):
            hi = mid                # mid might be the answer, keep it
        else:
            lo = mid + 1            # mid is too small, discard it
    return lo

C

int binary_search(int nums[], int n, int target) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {                  /* range still has at least one item */
        int mid = lo + (hi - lo) / 2;   /* avoids int overflow */
        if (nums[mid] == target) {
            return mid;                 /* found it */
        } else if (nums[mid] < target) {
            lo = mid + 1;               /* target is in the right half */
        } else {
            hi = mid - 1;               /* target is in the left half */
        }
    }
    return -1;                          /* range is empty: not found */
}

/* Variant: first index where condition flips from 0 to 1 */
int first_true(int lo, int hi, int (*condition)(int)) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (condition(mid)) hi = mid;   /* mid might be the answer */
        else lo = mid + 1;              /* mid is too small */
    }
    return lo;
}

Java

int binarySearch(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {                  // range still has at least one item
        int mid = lo + (hi - lo) / 2;   // avoids int overflow
        if (nums[mid] == target) {
            return mid;                 // found it
        } else if (nums[mid] < target) {
            lo = mid + 1;               // target is in the right half
        } else {
            hi = mid - 1;               // target is in the left half
        }
    }
    return -1;                          // range is empty: not found
}

// Variant: first index where condition flips from false to true
int firstTrue(int lo, int hi, java.util.function.IntPredicate condition) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (condition.test(mid)) hi = mid;   // mid might be the answer
        else lo = mid + 1;                   // mid is too small
    }
    return lo;
}

Complexity: Time O(log n) because the range halves every step; space O(1) for the iterative version (O(log n) if written recursively). If each check costs O(k), such as a feasibility test when searching on the answer, total time is O(k log n).

Programs that use it

Interview problems that use it

  • Search Insert Position: Find the first index whose value is greater than or equal to the target; that index is where the target is or would be inserted.
  • First and Last Position of an Element in a Sorted Array: Run binary search twice, once biased to keep moving left after a match and once biased to keep moving right, to find both edges of the run of equal values.
  • Search in a Rotated Sorted Array: At each step one half is always properly sorted; check whether the target lies in that sorted half and discard the other half accordingly.
  • Find Minimum in a Rotated Sorted Array: Compare the middle value to the rightmost value: if mid is larger, the minimum is to its right; otherwise it is at mid or to its left.
  • Square Root of an Integer (floor): Binary search the answer between 0 and x for the largest number whose square is not greater than x.
  • Minimum Eating Speed (Koko and the Bananas): Binary search the speed from 1 to the largest pile, using a quick check of how many hours that speed needs, to find the smallest speed that finishes in time.

Common mistakes

  • Infinite loops from the wrong boundary update: using lo = mid instead of lo = mid + 1 (or hi = mid with a lo <= hi loop) can leave the range unchanged forever. Pick one style, either 'lo <= hi with mid +/- 1' or 'lo < hi with hi = mid', and stay consistent.
  • Off-by-one errors in the loop condition or the initial hi: mixing hi = len(nums) with lo <= hi can read past the end of the array, while using lo < hi with hi = len - 1 can skip the last element. Test on arrays of size 0, 1 and 2.
  • Computing mid as (lo + hi) / 2 in languages with fixed-size ints, which can overflow on huge ranges. Use lo + (hi - lo) / 2. Also forgetting that the data must be sorted (or the condition must be monotonic) for the halving to be valid.

Frequently asked questions

When can I use binary search?

You can use it whenever you can look at one position and safely rule out half of the remaining candidates. The classic case is a sorted array, but it also works on any yes/no condition that is monotonic, meaning it is false for every value up to some point and true for every value after it (or the reverse).

Should I use lo <= hi or lo < hi?

Both work if you pair them with the right updates. Use lo <= hi with lo = mid + 1 and hi = mid - 1 when searching for an exact match. Use lo < hi with hi = mid and lo = mid + 1 when searching for the first position where a condition becomes true; the loop ends when lo == hi, and that index is your answer.

Does binary search work on unsorted data?

Not on plain unsorted arrays, because one comparison tells you nothing about which half to discard. It does work on some special structures, such as a rotated sorted array, and on 'search on the answer' problems where the feasibility check is monotonic, even though no array is sorted.

← All interview patterns

Try AI Flowchart free →