Skip to main content
Binary Search

Classic Search

Look at the middle element. If it's your target, done. If target is smaller, search the left half. If larger, search the right half. Repeat until found or the range is empty. O(log n).

O(log n)
·
O(1)

How It Works

Classic binary search locates a target in a sorted array by repeatedly halving the search space. Compare the middle element to the target: equal means done; if the target is smaller, discard the right half; if larger, discard the left. Two indices, low and high, bracket the live region, and each iteration eliminates half of it.

Because the candidate set shrinks geometrically, at most about log₂(n) comparisons are needed — around 30 probes suffice for a billion elements, versus n probes for linear scan. Implementation care matters: compute mid as low + (high − low) / 2 to avoid integer overflow, and pin down whether your loop invariant uses an inclusive or exclusive right bound to prevent off-by-one bugs.

Step-by-Step Visualization

Search for target = 9. Full array is our search space
L
1
0
3
1
5
2
mid
7
3
9
4
11
5
R
13
6
Target9
mid valuenums[3] = 7
1/4

Code

Java
static int binarySearch(int[] nums, int target) {
  int left = 0;
  int right = nums.length - 1;

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

    if (nums[mid] == target) {
      return mid;        // Found!
    } else if (nums[mid] < target) {
      left = mid + 1;    // Target is in right half
    } else {
      right = mid - 1;   // Target is in left half
    }
  }

  return -1; // Not found
}

// Example: binarySearch(new int[]{1, 3, 5, 7, 9, 11, 13}, 9)
// Answer: 4

Tips & Gotchas

1Always use left + Math.floor((right - left) / 2) to avoid integer overflow
2Be careful with the loop condition: left <= right (inclusive) vs left < right
3After the loop, left is the insertion point if target not found

Practice Problems

  • 1Binary Search
  • 2Search Insert Position
  • 3Guess Number Higher or Lower
  • 4Search a 2D Matrix

About the Binary Search Pattern

If the search space is sorted (or has a monotonic property), you can eliminate half of it with each comparison. This reduces O(n) linear search to O(log n). Works on arrays, answer spaces, and even abstract conditions.

Key insight

When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.

Common Array Interview Problems

  • Two Sum
  • Best Time to Buy & Sell Stock
  • Maximum Subarray
  • Merge Intervals
  • Product of Array Except Self
  • Container With Most Water

Frequently Asked Questions

What causes most binary search bugs?

Inconsistent loop invariants: mixing an inclusive high (while low <= high, high = mid − 1) with exclusive-style updates, or vice versa, leads to infinite loops or skipped elements. Pick one convention, write down what the interval means, and keep every update consistent with it.

Is binary search worth it if I have to sort the array first?

Sorting costs O(n log n), which dwarfs a single O(log n) search, so for one lookup a linear scan is better. Sorting pays off when you will search many times, since Q queries then cost O(n log n + Q log n) instead of O(n·Q).