Binary Search

Source: LeetCode: Introduction to Binary Search

https://leetcode.com/explore/learn/card/binary-search/

Binary Search should be considered every time you need to search for an index or element in a collection. If the collection is unordered, we can always sort it first before applying Binary Search.

Template 1 and 3 are the most commonly used and almost all binary search problems can be easily implemented in one of them. Template 2 is a bit more advanced and used for certain types of problems.

Template #1:

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: left > right
    return -1;
}

Distinguishing Syntax:

  • Initial Condition:left = 0, right = length-1
  • Termination:left > right
  • Searching Left:right = mid-1
  • Searching Right:left = mid+1

Template #2:

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

    int left = 0, right = nums.length;
    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 (left != nums.length && nums[left] == target) return left;
    return -1;
}

It is used to search for an element or condition which requires accessing the current index and its immediate right neighbor's index in the array.

Key Attributes:

  • An advanced way to implement Binary Search.
  • Search Condition needs to access element's immediate right neighbor
  • Use element's right neighbor to determine if 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.

Distinguishing Syntax:

  • Initial Condition:left = 0, right = length
  • Termination:left == right
  • Searching Left:right = mid
  • Searching Right:left = mid+1

Template #3:

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;
}

It is used to search for an element or condition which requires _accessing the current index and its immediate left and right neighbor's index _in the array.

Key Attributes:

  • An alternative way to implement Binary Search
  • Search Condition needs to access element's immediate left and right neighbors
  • Use element's neighbors to determine if condition is met and decide whether to go left or right
  • Gurantees 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.

Distinguishing Syntax:

  • Initial Condition: left = 0, right = length-1
  • Termination: left + 1 == right
  • Searching Left: right = mid
  • Searching Right: left = mid

results matching ""

    No results matching ""