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.