Lesson 11.1 · Binary Search
Halving the Search Space
Look at the middle, decide which half can't contain the answer, and throw it away: about 17 steps for 100,000 items.
12 min
Think of it like this
Guessing a number between 1 and 100 when your friend says "higher" or "lower": guess 50, then 75 or 25, and so on. You never need more than 7 guesses, because each one halves what's left.
1.The classic search
Keep lo and hi, the range that could still hold the target. Compute mid = lo + (hi − lo) / 2 (this form never overflows). If nums[mid] is the target, done; if it's smaller, the target can only be right of mid (lo = mid + 1); otherwise left (hi = mid − 1). When lo > hi the range is empty: not found.
public class Main {
static int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
public static void main(String[] args) {
int[] a = {-1, 0, 3, 5, 9, 12};
System.out.println(search(a, 9) + " " + search(a, 2));
System.out.println("steps for a million items: " + (int) Math.ceil(Math.log(1_000_000) / Math.log(2)));
}
}Output
4 -1
steps for a million items: 20nums = [-1, 0, 3, 5, 9, 12], target = 9Step 1/2mid = 2: 3 < 9, so the target is right of mid. lo = 3.
Remember
- O(log n): each step halves the range.
- mid = lo + (hi − lo) / 2.
- With
lo <= hi, update with mid + 1 / mid − 1.
Common mistakes
(lo + hi) / 2overflowing for huge indexes.- Infinite loops from
lo = midwithlo <= hi.