Move it step by step
Searching array [3, 8, 12, 17, 23, 31, 42, 56] for 42
- 30
- 81
- 122
- 173
- 234
- 315
- 426
- 567
- comparing
- found
- excluded
- current range
- The number under each box is its index
Binary search assumes the array is already sorted in ascending order. It won't search correctly on an unsorted array.
Step 1 of 7Comparisons: 0
We're looking for 42. The range covers the whole array, index 0 to 7.
The pseudocode line currently running
- 1lo = 0, hi = n - 1
- 2while lo <= hi:
- 3mid = (lo + hi) divided by 2, rounded down
- 4if a[mid] == x: return mid
- 5if a[mid] < x: lo = mid + 1
- 6else: hi = mid - 1
- 7return -1 (not found)
Change the example
Try predicting
You're on step 1.
Which index will be compared next?
What you'll learn
- The flow of comparing against the middle and narrowing the search range by half each time
- Why the number of comparisons stays small whether there are 8 elements or 1,000,000
Prerequisites
- The flow of linear search
- Arrays and indices (numbering that starts at 0)
- While loops, and integer division (the quotient)
How this search works
Binary search compares the target with the middle value of a sorted array, decides whether it must be on the left or right half, and narrows the range by half.
Since each comparison cuts the candidates in half, the number of comparisons barely increases even as the array grows larger.
Steps, with an example
- 1Set the range to the whole array (lo = 0, hi = the rightmost index)
- 2Compare the value at the middle of the range, mid, with the target value
- 3If they match, mid is the answer, and we're done
- 4If the middle value is smaller, narrow the range to the right half; if larger, narrow it to the left half
- 5If the range becomes empty, we finish with "not found"
| # | Range and middle | Result |
|---|---|---|
| 1 | Range 0–7Index 3: 17 | Smaller. Go right half |
| 2 | Range 4–7Index 5: 31 | Smaller. Go right half |
| 3 | Range 6–7Index 6: 42 | Same. Found |
Comparisons and complexity
| Case | Comparisons | Complexity |
|---|---|---|
| Best case | 1 comparison (the very first middle) | O(1) |
| Average | About log₂ n comparisons | O(log n) |
| Worst case | About log₂ n + 1 comparisons | O(log n) |
With 8 elements, the worst case is 4 comparisons; even with 1,000,000 elements, it's only about 20. Linear search would take up to 1,000,000 comparisons for 1,000,000 elements, so the gap is enormous.
| Target | Linear search | Binary search |
|---|---|---|
| 42 | 7 | 3 |
| 20 | 8 | 3 |
| 3 | 1 | 3 |
| 56 | 8 | 4 |
When to use it
Good fit
- The array is already sorted in ascending order
- You'll search the same array many times (sort it once up front, and every search after that is fast)
- You're looking for a boundary, like "the first position at or above this value"
Not a good fit
- The array isn't sorted (the cost of sorting it would outweigh the benefit)
- There are frequent insertions or deletions, making it hard to keep the array sorted
Code
Pseudocode
- 1lo = 0, hi = n - 1
- 2while lo <= hi:
- 3mid = (lo + hi) divided by 2, rounded down
- 4if a[mid] == x: return mid
- 5if a[mid] < x: lo = mid + 1
- 6else: hi = mid - 1
- 7return -1 (not found)
Working code
▶ Press “Run” to see the result here
Edit the Python or JavaScript and press “Run” to see the result right away. Java is read-only here.
FAQ
- What happens if you use this on an unsorted array?
- Since it decides left or right based on comparing with the middle, it can discard the side that actually holds the answer. It won't raise an error. It may simply report a value that's actually there as "not found".
- Why is the Java code's calculation of mid different?
- To prevent `lo + hi` from overflowing int's maximum value. `lo + (hi - lo) / 2` produces the same result without the addition ever overflowing.
- When there are two middle values, which one does it check?
- With an even number of elements, there are two middle values. Since this rounds the quotient down, it checks the left one.
