Binary Search Template

When writing code for binary search, one common challenge is dealing with off-by-one errors. These errors arise when determining the iteration conditions and deciding which elements to eliminate at each step of the search. Specifically:

• We have to decide when we should stop iterating. Imagine searching for 200 in a list of numbers 1-100. Our left and right will become closer and closer until some condition should tell us that our target doesn't exist. We need to to decide whether to iterate while left < right, left + 1 < right, or left <= right
• If we want to eliminate the left half of the remaining search space, we face the dilemma of whether to reassign the left pointer to mid or mid + 1.
• On the other hand, if we aim to remove the right half, we encounter the uncertainty of whether to reassign the right pointer to mid or mid - 1.

These off-by-one errors can introduce subtle bugs and cause headaches when implementing binary search. If not handled carefully, they can lead to incorrect results.

Template

To help mitigate off-by-one errors, we provide a reliable template for binary search implementations:

let left = 0;
let right = array.length - 1;

while (left <= right) {
  let mid = Math.floor((left + right) / 2);

  if (array[mid] === target) {
    // Optional early return
  } else if (***comparison***) {
    left = mid + 1;
  } else {
    right = mid - 1;
  }
}

// Most often, if the target is not found, additional handling
// or returning a specific value is needed. In many cases it will
// be the index that `left` variable holds, which would indicate
// where the target *would* fit into the array.

This template establishes the initial left and right pointers and sets up the binary search loop. The mid value is calculated as the average of the left and right indices. Based on the comparison between the mid element and the target, the pointers are adjusted accordingly to narrow down the search space. Once the loop concludes, additional handling can be performed based on whether the target was found or not.

While using the provided template is highly recommended to avoid off-by-one errors, if you choose to create your own implementation, it's crucial to stick with a consistent approach across different exercises. Switching back and forth between different implementations can introduce unnecessary complexity and confusion.

In the upcoming assignments, we will apply the binary search template to solve different problems, allowing you to see it in action and further solidify your understanding of this efficient search algorithm.