Find the bug · Easy

Fix the Binary Search

Easy Find the bug Most askedSeen at Google, Amazon, Microsoft

A teammate wrote search(nums, target): return the index of target in the sorted array nums (distinct values), or -1 if it is not there.

It passes most of their tests, but production logs show it sometimes returns -1 for values that are in the array. Find the bug and fix it. Keep the O(log n) running time.

Example 1

Input: nums = [1, 3, 5, 7, 9], target = 7
Output: 3

Example 2

Input: nums = [1, 3, 5, 7, 9], target = 9
Output: 4
Explanation: The buggy version returns -1 here.

The buggy code

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

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

def search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

<?php

function search(array $nums, int $target): int
{
    $lo = 0;
    $hi = count($nums) - 1;
    while ($lo < $hi) {
        $mid = intdiv($lo + $hi, 2);
        if ($nums[$mid] === $target) {
            return $mid;
        }
        if ($nums[$mid] < $target) {
            $lo = $mid + 1;
        } else {
            $hi = $mid - 1;
        }
    }
    return -1;
}

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }
}

Hints

Hint 1

Which targets fail? Try the first and last elements, and an array of length 1.

Hint 2

Look at the loop condition together with how hi is initialised: is the search range inclusive or exclusive?

Find and fix the bug

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the bug and the fix

Time O(log n) · Space O(1)

The bug: hi starts at nums.length - 1, so the range [lo, hi] is inclusive, but the loop runs while (lo < hi). When lo == hi there is still one candidate left and the loop exits without checking it. Targets at the end of the array (and single-element arrays) are missed.

The fix: pick one convention and use it consistently. With an inclusive range the loop must be while (lo <= hi) and the updates are lo = mid + 1 / hi = mid - 1. (With a half-open range you would start hi = nums.length and use while (lo < hi) with hi = mid.)

Interviewers ask this because almost every hand-written binary search has an off-by-one somewhere; saying out loud which invariant you keep ("the answer is always inside [lo, hi]") is what they listen for.

Fixed version

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

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

def search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1  # inclusive range [lo, hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

<?php

function search(array $nums, int $target): int
{
    $lo = 0;
    $hi = count($nums) - 1; // inclusive range [lo, hi]
    while ($lo <= $hi) {
        $mid = intdiv($lo + $hi, 2);
        if ($nums[$mid] === $target) {
            return $mid;
        }
        if ($nums[$mid] < $target) {
            $lo = $mid + 1;
        } else {
            $hi = $mid - 1;
        }
    }
    return -1;
}

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1; // inclusive range [lo, hi]
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }
}

Common mistakes

Fixing it by adding a special case for the last element instead of fixing the invariant.
Switching to while (lo <= hi) but keeping hi = mid, which loops forever.
(lo + hi) / 2 overflow in Java/C for very large arrays: use lo + (hi - lo) / 2.

Follow-up questions

Return the insertion position when the target is missing.
Find the first and last position of a target that can repeat.

Fix the Two Sum Hash Map · Easy
Fix the Longest Substring Without Repeats · Medium
Fix Merge Intervals · Medium
Fix the Mutable Default Argument · Easy
Fix the Substring Check · Easy
Fix the Median (JavaScript Sort) · Easy