Lower and Upper Bounds, Binary Search, and Related Algorithms

Jun 27, 2024

Lower and Upper Bounds, Binary Search, and Related Algorithms 📉

Lower Bound

  • Definition: The smallest index such that the number at that index is greater than or equal to the given number.
  • Requirement: The array must be sorted.
  • Example Process:
    • Given array: [1, 3, 5, 8, 10, 15]
    • If X = 8, smallest index is 3 (because 8 ≥ 8).
    • If X = 9, smallest index is 5 (because 15 ≥ 9).
    • If X = 16, index will be size of array as no element is ≥ 16.
  • Linear Search Method: Iterate through the array to find the element; this is inefficient with O(n) complexity.
  • Binary Search Method: Efficient, with O(log n) complexity, utilizes a sorted array to halve search space.
    • Initialize low to 0 and high to array length - 1.
    • Keep tracking a possible answer and adjust low and high based on comparisons.

Upper Bound

  • Definition: The smallest index such that the number at that index is greater than the given number.
  • Similar to Lower Bound but the condition changes to strictly greater (> instead of >=).
  • Implementation: Modify the lower bound binary search to check for strictly greater elements.
  • Example Process:
    • Given array: [1, 3, 5, 8, 10, 15]
    • If X = 6, smallest index is 3 (because 8 > 6).
    • If X = 11, smallest index is 5 (because 15 > 11).

Search Insert Position

  • Problem Statement: Given a sorted array and a target value, find the index where the target would be inserted to maintain sorted order.
  • Observation: This is equivalent to finding the lower bound for the target value.
  • Example:
    • Given array: [1, 3, 5, 7]
    • If target = 6, it should be inserted at index 3.
    • If target = 2, it should be inserted at index 1.

Floor and Ceiling in Sorted Array

  • Floor: The largest number in the array that is either equal to or less than X.
  • Ceiling: The smallest number in the array that is either equal to or greater than X.
  • Finding Floor: Modify lower bound to check for elements smaller than or equal to X and keep a possible answer.
  • Finding Ceiling: Equivalent to finding the lower bound for X.

Code Template for Lower Bound and Upper Bound (Conceptual Pseudocode)

Lower Bound

int lower_bound(vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1, answer = arr.size();
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] >= target) {
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return answer;
}

Upper Bound

int upper_bound(vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1, answer = arr.size();
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] > target) {
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return answer;
}

Using C++ STL for Lower and Upper Bounds

  • Lower Bound: 
    auto it = lower_bound(arr.begin(), arr.end(), X);
int index = it - arr.begin();
  • Upper Bound: 
    auto it = upper_bound(arr.begin(), arr.end(), X);
int index = it - arr.begin();
  • Replace .begin() and .end() with specific iterator bounds for subarrays if required.

Time Complexity

  • Both lower and upper bound implementations have a time complexity of O(log n) due to binary search.

Conclusion

  • Understanding lower bound and upper bound is crucial for efficient searching and problem-solving in sorted arrays.
  • Practice implementing and using these concepts to gain proficiency in handling coding rounds and real-world problems efficiently.

Full transcript