Binary Search: Search a Sorted Array

Compare the middle and keep one half

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

1. left and right are the first and last positions still worth checking. Start with the whole array.
2. If nums[mid] is the target, return mid. If it is smaller, every value to its left is also too small: move left to mid + 1.
3. If nums[mid] is larger, every value to its right is also too large: move right to mid - 1.
4. When left passes right, no positions remain. Return -1 because the target is missing.

Walk through finding 11

If the target were 8, the middle checks would be 7, 11, then 9. The last comparison moves right to 3 while left is 4. There is nothing left to check, so return -1.

When values repeat: find the first match

The basic code can return any matching position. For [1,3,3,7,9], it returns index 2 for target 3. If you need the first 3, do not stop at equality: keep looking left.

The version below finds the first position whose value is at least the target. This is called lower bound. For target 3 it returns 1; for target 4 it returns 3, where 4 would fit before 7.

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

• Here right starts at nums.length and is outside the searchable range. Use left < right, not the basic version's left <= right.
• If nums[mid] is at least the target, keep mid as a possible answer with right = mid. Otherwise skip it with left = mid + 1.
• If every value is smaller, return nums.length: the target would fit after the array. To check whether it exists, require index < nums.length and nums[index] === target.

Other problems that use the same idea

• Rotated arrays: [5,7,9,1,3] is not sorted from end to end. With distinct values, identify which half is sorted before choosing where to search. Duplicates can make the worst case linear.
• Sorted matrices: treat rows as one long sorted array only if each row is sorted and its first value exceeds the previous row's last value. Sorted rows alone are not enough.
• Searching possible answers: suppose a package capacity of 10 is enough to finish within a fixed number of days. Any larger capacity must also be enough. You can search for the smallest working capacity because answers change once from 'not enough' to 'enough', never back again.
• Longest Increasing Subsequence uses binary search on a sorted helper array, not on the original input. Learn that problem's helper meaning separately; its values are not necessarily an actual subsequence.

Time, space, and practical limits

• Sorted-array search takes O(log N) time for nonempty input and O(1) extra space. Each check roughly halves the remaining positions. Empty input takes constant time and returns -1 in the basic version.
• If you sort first, include that cost: comparison sorting typically takes O(N log N) and changes positions. For one lookup in unsorted data, a linear scan may be simpler.
• Searching possible answers also pays for each test. If testing one capacity costs O(N), multiply that by the number of search steps.
• Use Math.floor for the midpoint, not a bitwise shortcut: JavaScript bitwise operators convert numbers to 32-bit integers. Keep numeric bounds and calculations within the safe-integer range.

Mistakes and Counterexamples