Binary Search - Data Structures & Algorithms

Binary search is one of the most fundamental algorithms in computer science. We place it in the Trees & Tries group because it’s the same principle that makes BSTs fast — cut the search space in half each step.

In simple language, binary search is like looking up a word in a dictionary. We don’t start from page 1. We open the middle, see if we need to go left or right, and repeat. Each step eliminates half the remaining pages.

The Classic Binary Search

Given a sorted array, find if a target exists. The key word is sorted — binary search only works on sorted data.

function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2); // avoid overflow
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;  // target is in right half
    else hi = mid - 1;                     // target is in left half
  }
  return -1; // not found
}

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2       # avoid overflow
        if arr[mid] == target: return mid
        if arr[mid] < target: lo = mid + 1  # right half
        else: hi = mid - 1                   # left half
    return -1  # not found

int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;     // avoid overflow
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;  // right half
        else hi = mid - 1;                     // left half
    }
    return -1; // not found
}

Time: O(log n) — we halve the search space each iteration. Space: O(1).

Why `lo + (hi - lo) / 2` instead of `(lo + hi) / 2`?

Because lo + hi can overflow if both are large integers. lo + (hi - lo) / 2 is mathematically the same but safe from overflow.

The Off-by-One Problem

Binary search is notorious for off-by-one bugs. Here’s a mental model to avoid them:

Binary Search Decision Framework

Q1 Is the search space inclusive [lo, hi] or exclusive [lo, hi)?

Q2 Loop condition: lo <= hi (inclusive) or lo < hi (exclusive)?

Q3 When shrinking: mid + 1 / mid - 1 (inclusive) or mid + 1 / mid (exclusive)?

Tip: Pick ONE style and stick with it. The inclusive [lo, hi] style with lo <= hi is the most common in interviews.

First and Last Occurrence

Sometimes the target appears multiple times. We need the first or last index. The trick is: don’t stop when we find the target — keep narrowing.

First Occurrence (Lower Bound)

function firstOccurrence(arr, target) {
  let lo = 0, hi = arr.length - 1, result = -1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) {
      result = mid;     // record it
      hi = mid - 1;     // but keep searching left
    } else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return result;
}

def first_occurrence(arr, target):
    lo, hi, result = 0, len(arr) - 1, -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            result = mid       # record it
            hi = mid - 1       # keep searching left
        elif arr[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return result

int firstOccurrence(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1, result = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) {
            result = mid;       // record it
            hi = mid - 1;       // keep searching left
        } else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return result;
}

Last Occurrence (Upper Bound)

Same idea, but when we find the target, we search right instead.

function lastOccurrence(arr, target) {
  let lo = 0, hi = arr.length - 1, result = -1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) {
      result = mid;     // record it
      lo = mid + 1;     // keep searching right
    } else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return result;
}

def last_occurrence(arr, target):
    lo, hi, result = 0, len(arr) - 1, -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            result = mid       # record it
            lo = mid + 1       # keep searching right
        elif arr[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return result

int lastOccurrence(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1, result = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) {
            result = mid;       // record it
            lo = mid + 1;       // keep searching right
        } else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return result;
}

Search in Rotated Sorted Array

A rotated array is a sorted array that’s been “rotated” — like [4, 5, 6, 7, 0, 1, 2] (was [0, 1, 2, 4, 5, 6, 7]). The trick is that at least one half is always sorted.

Rotated Array: [4, 5, 6, 7, 0, 1, 2]

4 5 6 7 0 1 2

sorted half ↑ pivot sorted half

function searchRotated(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) return mid;
    if (arr[lo] <= arr[mid]) {           // left half is sorted
      if (target >= arr[lo] && target < arr[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {                              // right half is sorted
      if (target > arr[mid] && target <= arr[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

def search_rotated(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target: return mid
        if arr[lo] <= arr[mid]:            # left half sorted
            if arr[lo] <= target < arr[mid]: hi = mid - 1
            else: lo = mid + 1
        else:                               # right half sorted
            if arr[mid] < target <= arr[hi]: lo = mid + 1
            else: hi = mid - 1
    return -1

int searchRotated(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[lo] <= arr[mid]) {           // left half sorted
            if (target >= arr[lo] && target < arr[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {                              // right half sorted
            if (target > arr[mid] && target <= arr[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

Time: O(log n) — still halving each step. Space: O(1).

Find Peak Element

A peak element is greater than its neighbors. The array can have multiple peaks — we just need to find any one. The trick: if arr[mid] < arr[mid + 1], a peak must exist to the right (the values are still going up).

function findPeakElement(arr) {
  let lo = 0, hi = arr.length - 1;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] < arr[mid + 1]) lo = mid + 1;  // peak is to the right
    else hi = mid;                                // peak is at mid or left
  }
  return lo; // lo === hi, that's our peak
}

def find_peak_element(arr):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < arr[mid + 1]: lo = mid + 1  # peak is right
        else: hi = mid                              # peak is at mid or left
    return lo  # lo == hi, that's our peak

int findPeakElement(int[] arr) {
    int lo = 0, hi = arr.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < arr[mid + 1]) lo = mid + 1;  // peak is right
        else hi = mid;                                // peak is at mid or left
    }
    return lo; // lo == hi, that's our peak
}

Notice this uses lo < hi instead of lo <= hi. That’s because we’re not looking for a specific value — we’re narrowing down to a single index.

When to Recognize Binary Search

Binary search isn’t just for sorted arrays. It works whenever we can define a monotonic condition — something that’s false for a while, then becomes true forever (or vice versa). Some clues:

“Find the minimum/maximum that satisfies…”
“Find the first/last occurrence of…”
The problem involves a sorted or semi-sorted structure
We can define a yes/no question where the answer flips at some boundary

Key Takeaways

Binary search requires a sorted (or semi-sorted) structure. Always verify this.
Use lo + (hi - lo) / 2 to avoid integer overflow.
For first/last occurrence: don’t stop when we find the target, keep narrowing.
For rotated arrays: identify which half is sorted, then check if the target is in that sorted half.
Pick one loop style (lo <= hi with mid +/- 1, or lo < hi with mid / mid + 1) and be consistent.

In simple language, binary search is just repeatedly asking “should I go left or right?” Each answer eliminates half the options. The hard part isn’t the algorithm itself — it’s getting the boundary conditions right.