Note

In the while loop

• we use $<$ when the search space reduces without including the middle element after each iteration.
  • left can never equal right within the loop.
  • Once left equals right, the loop stops, and we have narrowed it down to a single element.
  • We typically use right = mid (instead of mid - 1) because mid could still be part of the search space.
• We use $\leq$ when you want to include both left and right as valid indices in the search space. This means the search continues until left goes strictly beyond right.
  • left can equal right within the loop.
  • The loop will stop when left surpasses right (left > right).
  • Here, right = mid - 1 because mid has been ruled out as the target when arr[mid] > target.
  • When the entire range from left to right needs to be processed.
  • This variant is often used when searching for an exact match (i.e., you're looking for a specific target value, and you want to include all possible indices).

Intro

Because Binary Search operates by applying a condition to the value in the middle of our search space and thus cutting the search space in half, in the worse case, we will have to make O(log n) comparisons, where n is the number of elements in our collection.

Why log n?

• Binary search is performed by dividing the existing array in half.
• So every time you a call the subroutine ( or complete one iteration ) the size reduced to half of the existing part.
• First N become N/2, then it become N/4 and go on till it find the element or size become 1.
• The maximum no of iterations is log N (base 2).

Although Binary Search does require keeping track of 3 indices, the iterative solution does not typically require any other additional space and can be applied directly to the collection itself, therefore warrants O(1) or constant space.

A successful binary search has 3 parts:

• Collection is sorted
• Loop or recursion search
• Determine viable candidates the in remaining space

Templates

Template 1

SQRT, Search In Rotated Sorted Array

Template #1 is used to search for an element or condition which can be determined by accessing a single index in the array.

• Most basic and elementary form of Binary Search
• Search Condition can be determined without comparing to the element's neighbors (or use specific elements around it)
• No post-processing required because at each step, you are checking to see if the element has been found. If you reach the end, then you know the element is not found

int binarySearch(int[] nums, int target){
    if(nums == null || nums.length == 0)
        return -1;

    int left = 0, right = nums.length - 1;
    while(left <= right){
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if(nums[mid] == target){ return mid; }
        else if(nums[mid] < target) { left = mid + 1; }
        else { right = mid - 1; }
    }
    // End Condition: r + 1 == l => l > r
    return -1;
}

Template 2

Find Peak, Find Minimum In Rotated Sorted Array

• An advanced way to implement Binary Search.
• Use the element's right neighbor to determine if the condition is met and decide whether to go left or right
• Guarantees Search Space is at least 2 in size at each step
• Post-processing required. Loop/Recursion ends when you have 1 element left. Need to assess if the remaining element meets the condition.

int binarySearch(int[] nums, int target){
    if(nums == null || nums.length == 0)
        return -1;

    int left = 0, right = nums.length - 1;
    while(left < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if(nums[mid] == target){ return mid; }
        else if(nums[mid] < target) { left = mid + 1; }
        else { right = mid; }
    }
    
    // Post-processing:
    // End Condition: left == right
    if(nums[left] == target) return left;
    return -1;
}

Template 3

Search For Range, Find K Closest Elements

• An alternative way to implement Binary Search
• Use the element's neighbors to determine if the condition is met and decide whether to go left or right
• Guarantees Search Space is at least 3 in size at each step
• Post-processing required. Loop/Recursion ends when you have 2 elements left. Need to assess if the remaining elements meet the condition.

int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0)
        return -1;

    int left = 0, right = nums.length - 1;
    while (left + 1 < right){
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if(nums[left] == target) return left;
    if(nums[right] == target) return right;
    return -1;
}