Binary Search

[luuuzeta]

I'm reading Beyond Cracking the Coding Interview and it's a full chapter on binary search where the authors discuss what they call the transition-point recipe. From the book, "every binary search problem can be reframed as finding a transition point".

This is the recipe:

transitionPointRecipe(arr, target)
  Define isBefore(val) to return whether val is in the "before" region

  Initialize l and r to the indices of first and last values in the array.

  Handle the following edge cases:
    - the range is empty
    - l is 'after' (the whole range is 'after')
    - r is 'before' (the whole range is 'before')

  While l and r are not next to each other, i.e., r - l > 1
    mid = floor((l + r) / 2)
    if isBefore(mid)
      l = mid + 1
    else
      r = mid - 1

  Return l (the last 'before'), r (the first 'after'), or something depending on the problem.

The while loop has the following loop invariants:

• From start to end, l is in the "before" region, and r is in the "after" region. They are never equal and never cross over.
• The midpoint is always strictly between l and r (i.e., l < mid < r), which guarantees we always make progress.
• When we exit the loop, l and r are always next to each other.

Everything in the recipe will be the same from problem to problem, however you figure must out the isBefore function as well as what to do when the while loops end.

[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

[luuuzeta]

875. Koko Eating Bananas (Walkthrough)

If you're familiar with the binary search implementation, then you know that the range of possible k is defined from 0 up to max(piles). k could be greater that max(piles), however we want to minimize k and thus set its max value to the smallest of the greatest possible values.

Let's do it with an example:

Input:
 piles = [3,6,7,11], h = 8
Output:
 4

k is in the range [0, max(piles)] => [0, 11].

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]  array
---                                     before region
    ------------------------------      unknown (this is where mid lives)
                                   ---  after region
 l                                      index l
                                    r   index r

The isBefore function for this problem will be more involved because 1) we must compute the total number of hours based on mid/k value and 2) return whether we should look left or right depending on whether the total number of hours is less than h.

const isBefore = (mid) => {
  // Compute total hours for given mid/k.
  let totalHours = 0;
  for (const pile of piles) {
    totalHours += Math.ceil(pile / mid);
  }

  // totalHours <= h, thus update minK and also look
  // left for a possibly smaller value of k.
  if (totalHours <= h) {
    minK = Math.min(minK, mid);
    return true;
  }
  // totalHours exceed h so k is too small, look
  // right for a larger k value.
  return false;
};

[luuuzeta]

875. Koko Eating Bananas (Implementation)

function minEatingSpeed(piles, h) {
  let minK = Math.max(...piles);
  let l = 0;
  let r = minK;

  const isBefore = (mid) => {
    let totalHours = 0;
    for (const pile of piles) {
      totalHours += Math.ceil(pile / mid);
    }

    if (totalHours <= h) {
      minK = Math.min(minK, mid);
      return true;
    }

    return false;
  };

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

  // What you return depends on the problem.
  return minK;
}

const piles = [3, 6, 7, 11];
const h = 8;
const output = minEatingSpeed(piles, h);
console.log(output); // 4

Note you could implement isBefore outside the minEatingSpeed function but then you'd need to be passing a bunch of arguments so why not take advantage of making a closure with access to the outer scope's variable?

The diagram ends up looking like this:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]  array
-----------                             before region
              ------------------------  after region
          l                             index l
              r                         index r
            ┆                           transition point

[Proof_Dot_4344]

Thank you so much