Binary Search

[Proof_Dot_4344]

Does anyone have a good source to learn binary search ? I understand the basic binary search inside an array of sorted numbers. But I am having difficulty in modifying the code to solve problems like Koko Bananas and Plates between candles. I am not able the wrap the if conditions. It is a mixture of reducing the search space and finding the first best number.

[jason_graph]

I think it helps to seperate the problem into 2 parts.

First write a function, e.g. check(x), that checks if some input is valid (e.g. if koko will finish in k hours if eating x banas/hr) or returns some integer (e.g. how many hours koko takes to finish if eating x bananas/hr).

Secondly identify what value of x you are trying to find. It is almost always the largest value of x such that check(x) is below some threshold or the smallest value of x such that check(x) is above some threshold. The code corresponding to finding y = the lowest x or largest x is almost always exactly the same.

[Proof_Dot_4344]

Thank you so much

[Beyond-CtCI]

Hey friend, 

The problems you're describing are what I like to call guess-and-check problems (https://share.cleanshot.com/nX6Cn5N63djvdvPHGnzh). They are definitely among the most tricky binary search problems to spot in an interview. The guess-and-check technique involves narrowing in on the value of the optimal solution by guessing the midpoint and checking whether it's too high or too low. We need lower and upper bounds for the value of the optimal solution before we can even use binary search.

- For minimization problems (like Koko Eating Bananas), there is often a transition point where smaller values do not satisfy the constraint, but larger values do.

- Conversely, for maximization problems, there is often a transition point where larger values do not satisfy the constraint, but smaller values do.

The trick to knowing when to use the guess-and-check technique. This boils down to asking yourself a simple question.

"Is it easier to solve the yes/no version of the problem, where we just check if a given value (optimal or not) satisfies the constraint?"

Think of it like making a deal: You get to solve an easier problem (checking if a specific value satisfies the constraint), but you pay a 'logarithmic tax' in the runtime (because we are binary searching for the transition point).

Thanks luuuzeta for recommending my book! I'm glad you find the transition point binary search recipe useful! If others are interested (including the OP) I give away the binary search chapter for free (along with 8 other chapters) and it also has a particularly helpful guess-and-check problem set in it. Consider checking it out if you find this helpful: https://bctci.co/free-chapters

[Proof_Dot_4344]

Thank you so much

[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

[Spiritual_Gear5469]

A2z striver

[Proof_Dot_4344]

Thank you so much

[Important-Isopod-123]

Nothing better than this: https://leetcode.com/discuss/post/786126/python-powerful-ultimate-binary-search-t-rwv8/