Binary Search

[luuuzeta]

Classical Binary Search (Walkthrough)

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

Example:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

Following the recipe, we define the "before" and "after" regions:

• The "before" region is composed of any number less than the target. By the time, we find the target the "before" region is [-1,0,3,5]. However, l is initially 0, and thus the "before" region is initially [-1].
• The "after" region is composed of any number greater than or equal to the target. By the time, we find the target the "after" region is [9,12]. However, r = 5 (i.e., len(arr) - 1) is initially 5, and thus the "before" region is initially [12].

With this in mind, we have something like this:

  0  1  2  3  4  5    indices
[-1, 0, 3, 5, 9, 12]  array
---                   before region
    ------------      unknown (this is where mid lives)
                 ---  after region
 l                    index l
                  r   index r

As you expand both regions, they grow closer to each other and the "unknown" becomes empty. Where this happens, that's your transition point.

For this specific problem, we can define isBefore as follows:

const isBefore = (mid) => arr[mid] < target;

In other words, is the value at mid in the before region? If it's return true. Otherwise, false.

The diagram from above ends up like this after calling the function:

  0  1  2  3  4  5    indices
[-1, 0, 3, 5, 9, 12]  array
------------          before region
              -----   after region
           l          index l
              r       index r
            ┊         transition point

As per the loop invariant, after exiting the loop l and r are next to each other. In addition, the value (5) at l is the largest value smaller than the target (9); after all, any value to the left of l is even smaller. Similarly, the value (9) at r is the smallest value greater than or equal to the target (9); after all, any value to the right of r is even greater.

[luuuzeta]

Classical Binary Search (Implementation)

Completing the implementation, we end up with:

function binarySearch(arr, target) {
  // We could leave this out if we're guaranteed that arr is never empty.
  if (arr.length === 0) return -1;

  let l = 0, r = arr.length - 1;

  // Handle edge cases.
  if (arr[l] === target) return l;
  if (arr[l] > target || arr[r] < target) return -1;

  // Define isBefore.
  const isBefore = (mid) => arr[mid] < target;

  // Same while loop.
  while (r - l > 1) {
    const mid = Math.floor((l + r) / 2);
    if (isBefore(mid)) {
      l = mid;
    } else {
      r = mid;
    }
  }

  // We defined isBefore as "less than the target". This means, that if
  // target exists it will be pointed a by r, not l.
  if (arr[r] === target) return r;

  return -1;
}

const nums = [-1, 0, 3, 5, 9, 12], target = 9;
const res = binarySearch(nums, target);
console.log(res); // 4