SyntaxShelf
DSA

Binary Search

Interview Prep · 6 entries

Binary Search — Basic Template

syntax
lo = 0, hi = n - 1
while lo <= hi:
  mid = lo + (hi - lo) // 2
  if found: return mid
  if target > arr[mid]: lo = mid + 1
  else: hi = mid - 1
return -1 (not found)
example
// JavaScript
function search(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[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

# Python
def search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
output
search([1,3,5,7,9,11,13], 9) → 4

Note Time O(log n), Space O(1). Use lo <= hi for exact match search. After the loop, lo is the insertion point (where target would go). This is equivalent to Python's bisect_left when target is not found. Memorize this template cold.

binary search templatebasic binary searchsearch sorted arraybisect

Search in Rotated Sorted Array

syntax
Array was sorted then rotated. One half is always sorted.
Determine which half is sorted, check if target is in that half.
example
// JavaScript
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;
    // Left half is sorted
    if (arr[lo] <= arr[mid]) {
      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;
}

# Python
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
output
search_rotated([4,5,6,7,0,1,2], 0) → 4

Note Time O(log n). Key insight: at least one half is always sorted after rotation. The condition arr[lo] <= arr[mid] determines which half. Edge case: duplicates make worst case O(n) since you cannot determine the sorted half. Very commonly asked.

rotated sorted arraysearch rotatedbinary search rotatedpivot search

Find First and Last Position

syntax
Two binary searches: one for leftmost occurrence, one for rightmost.
Leftmost: when found, keep searching left (hi = mid - 1).
Rightmost: when found, keep searching right (lo = mid + 1).
example
// JavaScript
function searchRange(arr, target) {
  return [findFirst(arr, target), findLast(arr, target)];
}

function findFirst(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; hi = mid - 1; }
    else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return result;
}

function findLast(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; lo = mid + 1; }
    else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return result;
}

# Python
def search_range(arr, target):
    def find_bound(is_left):
        lo, hi, result = 0, len(arr) - 1, -1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if arr[mid] == target:
                result = mid
                if is_left:
                    hi = mid - 1
                else:
                    lo = mid + 1
            elif arr[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return result
    return [find_bound(True), find_bound(False)]
output
search_range([5,7,7,8,8,10], 8) → [3, 4]

Note Time O(log n) for each search, O(log n) total. This is essentially bisect_left and bisect_right in Python. The count of target = last - first + 1. Follow-up: can also be used to count occurrences in a sorted array in O(log n).

first and last positionleftmost binary searchrightmost binary searchbisect left right

Search Insert Position

syntax
Find the index where target would be inserted to keep array sorted.
This is the standard binary search — when target is not found, lo is the answer.
example
// JavaScript
function searchInsert(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[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return lo; // insertion point
}

# Python
import bisect

def search_insert(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return lo

# Or simply: bisect.bisect_left(arr, target)
output
search_insert([1,3,5,6], 5) → 2
search_insert([1,3,5,6], 2) → 1
search_insert([1,3,5,6], 7) → 4

Note Time O(log n). After the while loop exits, lo == hi + 1 and lo is exactly where target belongs. This is equivalent to bisect_left in Python. Understanding why lo is the insertion point deepens your binary search intuition.

search insert positioninsertion pointbisect leftbinary search insert

Find Peak Element

syntax
A peak is greater than its neighbors.
Binary search: compare mid with mid+1.
If mid < mid+1, peak is to the right. Otherwise, peak is to the left (or mid itself).
example
// JavaScript
function findPeak(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; // mid could be the peak
    }
  }
  return lo; // lo === hi, pointing to a peak
}

# Python
def find_peak(arr):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < arr[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return lo
output
find_peak([1,2,3,1]) → 2 (peak is 3 at index 2)
find_peak([1,2,1,3,5,6,4]) → 5 (peak is 6 at index 5)

Note Time O(log n). Note: use lo < hi (not lo <= hi) because we narrow to a single element. The problem guarantees arr[-1] = arr[n] = -infinity conceptually. Multiple peaks may exist — this finds any one of them.

peak elementfind peakbinary search peakmountain array

Binary Search on the Answer

syntax
When the answer is a number in a range and you can verify feasibility:
1. Define search range [lo, hi] for the answer
2. Binary search: check if mid is a feasible answer
3. Narrow the range based on feasibility
example
// JavaScript — Minimum capacity to ship packages in d days
function shipWithinDays(weights, days) {
  let lo = Math.max(...weights); // must fit largest package
  let hi = weights.reduce((a, b) => a + b, 0); // ship everything in 1 day
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (canShip(weights, days, mid)) {
      hi = mid; // try smaller capacity
    } else {
      lo = mid + 1; // need more capacity
    }
  }
  return lo;
}

function canShip(weights, days, capacity) {
  let daysNeeded = 1, currentLoad = 0;
  for (const w of weights) {
    if (currentLoad + w > capacity) {
      daysNeeded++;
      currentLoad = 0;
    }
    currentLoad += w;
  }
  return daysNeeded <= days;
}

# Python
def ship_within_days(weights, days):
    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_ship(weights, days, mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

def can_ship(weights, days, capacity):
    days_needed, current_load = 1, 0
    for w in weights:
        if current_load + w > capacity:
            days_needed += 1
            current_load = 0
        current_load += w
    return days_needed <= days
output
ship_within_days([1,2,3,4,5,6,7,8,9,10], 5) → 15

Note Time O(n * log(sum - max)). This is an advanced pattern: instead of searching an array, you binary search the answer space. Works when: the feasibility function is monotonic (if capacity X works, X+1 also works). Other applications: minimum speed to eat bananas, split array largest sum.

binary search on answerminimize maximumfeasibility checkcapacity to shipsplit array