Binary Search

Usually, we would have to traverse through every element O(n) to find a target in a group. However, when our elements are sorted, we can cut the aspects we’re looking at in half. Fewer elements = faster search time. Binary search has a search time of O(log n).

Implementation

let search = (nums, target) => {
    let low = 0, high = nums.length-1;
    while (low < high){
        let mid = low + Math.floor((high - low + 1)/2);
        if (target < nums[mid]){
            high = mid - 1
        } else {
            low = mid;
        }
    }
    return nums[low] == target ? low : -1;
};

search([-1,0,3,5,9,12], 9)
//result: 4

How it works

Boundaries

First, we define two variables that store the indexes of our upper and lower limits. Initially, we set the boundary to the entire array.

let low = 0, high = nums.length-1;

Middle element

The ‘mid’ variable points to the central element within our boundary. This essentially splits our limit into two parts. This is where binary search saves time by cutting the elements searched in half.

let mid = low + Math.floor((high - low + 1)/2);

We run a conditional to check if our target is less than our mid; if so, we adjust our upper limit to our mid index. If our target is greater than mid, we adjust our lower limit to our mid index.

if (target < nums[mid]){
    high = mid - 1
    } else {
    low = mid;
    }

Loop

We use a ‘While’ loop to keep shrinking the boundary, narrowing our search pool. The loop exits when high = low, indicating only one element remains.

while (low < high){

Checking target

Finally, the mid variable has narrowed down to our target. We’ll perform a check to confirm we’ve found our target. Using a ternary operator and returning -1 if it is not our target.

return nums[low] == target ? low : -1;

Important Considerations

1. Don’t overflow the ‘mid’ calculation.

• Calculating ‘mid’ can result in overflow with large numbers.
• We have to decide if we’re using ‘left mid’ or ‘right mid.’

let mid = Math.floor((low + high) / 2) // Overflow very likely

let mid = low + Math.floor((high + low) / 2) // less likely, still possible

• Choosing left/lower or right/upper mid

let mid = low + Math.floor((high - low) / 2) // left/lower

let mid = low + Math.floor((high - low + 1) / 2) // right/upper

2. While loop logic

• Always use logic where ‘mid’ is excluded.
• mid is excluded: high = mid + 1
• mid is included: high = mid

3. Shrink logic

• I always use While(low < high) because the loop only exits on the condition of low = high. Pointing to the same element, which always exists.

4. Avoiding the infinity loop

• Miscalculating ‘mid’ and choosing the wrong shrink logic can lead to an infinity loop, and the function will never finish execution.

let mid = low + ((high - low) / 2) // Bad! We should use right/upper mid

if (target < nums[mid]){
    high = mid - 1
} else {
    low = mid
}

• The logic will keep shrinking itself to itself, and the program gets stuck. We need at least one element excluded.

let mid = low + ((high - low + 1) / 2); // Bad! We should use left/lower mid

if (target > nums[mid]) {
    low = mid + 1; // mid excluded
} else {
    high = mid; // mid included
}