Binary Search Overview

Pain Points

  1. Ambiguous Positioning: Traditional binary search might return any occurrence of the target value, which can be problematic when dealing with duplicate elements.
  2. Edge Cases: Handling arrays with small sizes (e.g., 1 or 2) might require additional condition checks.
  3. Infinite Loops: Incorrectly implemented conditions or updates for pointers might lead to infinite loops.

An optimized binary search algorithm ensures:

  • Always returning the first occurrence of the target value in arrays with duplicate elements.
  • Efficiently handling edge cases and avoiding infinite loops.
  • Maintaining interval consistency for reliable search space reduction.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binarySearch(int[] array, int target) {
    int left = 0;
    int right = array.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (array[mid] == target) {
            // Additional logic for specific variations
        } else if (array[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    // Post-processing to find the exact element or return a specific value
}

Applicable LeetCode Problems

  • Find First and Last Position of Element in Sorted Array (LeetCode 34)
  • Search Insert Position (LeetCode 35)
  • Find Minimum in Rotated Sorted Array (LeetCode 153)
  • … and many more problems involving searching in sorted arrays.

Binary Search Problem Types

  1. Standard Binary Search: Find the position of an element.
  2. Rotated Sorted Array: Identify pivot points or search elements in a rotated sorted array.
  3. Search in Unknown Size Array: Implement binary search when the size of the array is unknown.
  4. Two-Dimensional Binary Search: Apply binary search in 2D arrays or matrices.

Common Mistakes and Tips

  • Midpoint Calculation: Use mid = left + (right - left) / 2 to avoid integer overflow.
  • Update Statements: Ensure that left and right pointers are updated correctly inside the loop to avoid infinite loops.
  • Return Statement: Be mindful of what to return when the element is not found (e.g., -1 or left).

Interval Consistency Principle

  • Definition: Ensuring that the search space is reduced in a consistent manner in each iteration.
  • Importance: Maintains the reliability of the search and avoids missing potential solutions.
  • Application: Ensure that the update rules for left and right pointers and the conditions for checking elements are coherent and maintain a consistent search space.
  • http://www.cppblog.com/converse/archive/2009/10/05/97905.aspx

Example: Find the Rightmost Element

To modify the binary search to always return the rightmost occurrence of an element, you can slightly adjust the condition checks and updates in the algorithm.

Java Template for Rightmost Element

int binarySearchRightmost(int[] array, int target) {
    int left = 0;
    int right = array.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (array[mid] == target) {
            left = mid + 1;  // Move towards the right even if the target is found
        } else if (array[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    // Post-processing: Check if the rightmost element is indeed the target
    if (right >= 0 && array[right] == target) {
        return right;
    }
    return -1;
}