Binary Search Introduction

This section we'll learn how can binary search can be used to solve different type of problems

Two Types of Binary Search

There are two common types of binary search that we can use to solve different kinds of problems:

1. Type 1: low <= high
2. Type 2: low < high

When to Use Each Type

• Type 1 works well for problems where we are looking for an exact item, like a simple search.
• Type 2 works well for problems where we need to eliminate a section of the array at each step. A good example is finding the peak of a sorted (or rotated) array. If we try to solve this kind of problem using Type 1, it usually needs a lot of extra edge cases to handle correctly.

The Main Difference

• In Type 1, we ask: "Is the current number equal to the target?"
• In Type 2, we ask: "Which half of the array can we eliminate?"

In Type 2, once low and high become equal, that position is our answer.

Type 1 Template

let start = 0;
let end = arr.length - 1;

while (start <= end) {
    let mid = start + Math.floor((end - start) / 2);

    if (arr[mid] === target) {
        return true;
    } else if (arr[mid] < target) {
        start = mid + 1;
    } else {
        end = mid - 1;
    }
}

Type 2 Template

let start = 0;
let end = arr.length - 1;

while (start < end) {
    let mid = start + Math.floor((end - start) / 2);

    if (condition()) {
        start = mid + 1;
    } else {
        end = mid;
    }
}

Here, condition() stands for whatever check is needed for the specific problem — for example, comparing arr[mid] to a neighboring value to decide which half of the array can be safely eliminated.

When the loop ends, start and end will be equal, and that position holds the answer.