# 3.6 Binary Search

> On a sorted array, check the middle, then throw away the half that cannot contain the key. Each step halves the problem, so it takes O(log n).

Chapter: Simple Sorting & Searching · ~40 min · medium
URL: https://dsa.fetehadin.com/learn/binary-search

## Mental model

Guess-my-number from 1 to 100: you say 50; "higher"; 75; "lower"; 62… Every guess **cuts the possibilities in half**. You'll always win within 7 guesses. That's binary search.

### The algorithm (array must be sorted)

1. `low = 0`, `high = n - 1`.
2. While `low <= high`:
   - `mid = (low + high) / 2`
   - if `a[mid] == key` → found.
   - if `a[mid] < key` → the key can only be on the right: `low = mid + 1`.
   - else → it can only be on the left: `high = mid - 1`.
3. If the loop ends, the key isn't there: return −1.

### Why O(log n)

After each comparison the range halves: n → n/2 → n/4 → … → 1. The number of halvings is **log₂ n**. For a million items that's about **20 comparisons** instead of a million.

### Two requirements

- **Sorted** data, otherwise discarding a half is wrong.
- **Random access** (an array), so jumping to `mid` is O(1). On a linked list, reaching the middle costs O(n), which ruins the speed.

## C++ code: binary-search.cpp (iterative)

```cpp
#include <iostream>
using namespace std;

int binarySearch(const int a[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;   // same as (low+high)/2, but cannot overflow
        if (a[mid] == key) return mid;
        else if (a[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main() {
    int a[] = {3, 8, 12, 17, 23, 31, 38, 45, 52, 60};   // must be sorted
    int n = 10;
    cout << "search 38 -> " << binarySearch(a, n, 38) << "\n";
    cout << "search 3  -> " << binarySearch(a, n, 3) << "\n";
    cout << "search 40 -> " << binarySearch(a, n, 40) << "\n";
}
```

Expected output:

```text
search 38 -> 6
search 3  -> 0
search 40 -> -1
```

## Complexity

| Case | Cost |
| --- | --- |
| Best case | O(1): key is at the first mid |
| Average / worst case | O(log n): about ⌊log₂ n⌋ + 1 comparisons |
| 1,000,000 items | at most 20 comparisons |
| Needs sorted data? | Yes, and random access (an array, not a linked list) |

Space: O(1) iterative · O(log n) recursive (call stack)

## Videos

- [What is binary search](https://youtu.be/j5uXyPJ0Pew) (mycodeschool): Builds the idea from scratch and writes careful code including the edge cases.
- [Binary search in 4 minutes](https://youtu.be/fDKIpRe8GW4) (Michael Sambol): Four-minute visual summary.

## Exam lens

Likely questions:

- Trace binary search for key 23 in `2, 5, 8, 12, 16, 23, 38, 56, 72, 91`, giving low, mid and high at each step.
- Write an iterative binary search function in C++.
- What is the worst-case number of comparisons for n = 1024?
- Why can't binary search be applied to a linked list efficiently?

Common mistakes:

- Using `while (low < high)` instead of `low <= high`. That misses a key when one item is left.
- Setting `low = mid` or `high = mid` instead of `mid ± 1`, which can loop forever.
- Running it on unsorted data. The result is meaningless.
- `(low + high) / 2` can overflow for huge arrays; `low + (high - low) / 2` is safe.

## Quick check

1. Maximum comparisons for binary search on 1000 items?
   A. 10
   B. 100
   C. 500
   D. 1000
   Answer: A. 2¹⁰ = 1024 ≥ 1000, so about 10 halvings.

2. In `3, 8, 12, 17, 23, 31, 38`, searching 31: what is the first mid?
   A. index 2 (12)
   B. index 3 (17)
   C. index 4 (23)
   D. index 5 (31)
   Answer: B. (0 + 6) / 2 = 3.

3. If `a[mid] < key`, the next step is…
   A. high = mid − 1
   B. low = mid + 1
   C. low = mid
   D. return mid
   Answer: B. The key must be to the right of mid.

4. Binary search requires…
   A. a linked list
   B. a sorted array
   C. unique values
   D. an even n
   Answer: B. Sorted order lets us discard a half; an array gives O(1) access to mid.

## Practice

**Trace by hand.** Trace binary search for 23 and for 50 in `2, 5, 8, 12, 16, 23, 38, 56, 72, 91` (indices 0–9).

Solution:

**Key 23:** (0,9) mid 4 = 16 → low 5 · (5,9) mid 7 = 56 → high 6 · (5,6) mid 5 = 23 ✓ **3 comparisons**

**Key 50:** (0,9) mid 4 = 16 → low 5 · (5,9) mid 7 = 56 → high 6 · (5,6) mid 5 = 23 → low 6 · (6,6) mid 6 = 38 → low 7 · low > high → **−1 after 4 comparisons**


**Implement it.** Write `firstOccurrence(a, n, key)` that returns the **first** index of key in a sorted array with duplicates.

Hint: When `a[mid] == key`, don't return. Record `ans = mid` and keep searching left with `high = mid - 1`.

```cpp
int firstOccurrence(const int a[], int n, int key) {
    int low = 0, high = n - 1, ans = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == key) { ans = mid; high = mid - 1; }
        else if (a[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return ans;
}
```


**Problems:**

- [Binary Search](https://leetcode.com/problems/binary-search/) (easy). Hint: The textbook version. Get it right without looking.
- [Search Insert Position](https://leetcode.com/problems/search-insert-position/) (easy). Hint: When the loop ends without finding the key, `low` is exactly where it would be inserted.
- [First Bad Version](https://leetcode.com/problems/first-bad-version/) (easy). Hint: Binary search on the *answer*. Same pattern as firstOccurrence.

## Mastery checklist

- [ ] I can trace low, mid and high by hand.
- [ ] I can write iterative binary search with the correct `<=` and `± 1`.
- [ ] I can explain why it is O(log n) and needs sorted data.
- [ ] I can modify it to find the first occurrence.