Binary Search

The template that avoids off-by-one bugs — and why mid = lo + (hi-lo)//2

Binary search halves the search space every step. The subtle part is the loop condition and mid calculation. `lo + (hi - lo) // 2` avoids integer overflow that `(lo + hi) // 2` can cause in C++/Java.

Language:

Python

All languages — Exact match

JavaScript

function binarySearch(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return mid;
    else if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

console.log(binarySearch([1,3,5,7,9], 7));  // 3
console.log(binarySearch([1,3,5,7,9], 6));  // -1

TypeScript

function binarySearch(nums: number[], target: number): number {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return mid;
    else if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

Java

public static int binarySearch(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;   // safe: no overflow
        if (nums[mid] == target)      return mid;
        else if (nums[mid] < target)  lo = mid + 1;
        else                          hi = mid - 1;
    }
    return -1;
}

// Java stdlib:
Arrays.binarySearch(nums, target);  // returns index or negative

func binarySearch(nums []int, target int) int {
    lo, hi := 0, len(nums)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return -1
}

// stdlib: sort.SearchInts(nums, target)

C++

int binarySearch(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // safe: no overflow
        if (nums[mid] == target)      return mid;
        else if (nums[mid] < target)  lo = mid + 1;
        else                          hi = mid - 1;
    }
    return -1;
}

// stdlib: lower_bound(nums.begin(), nums.end(), target)