Skip to content
Searching for Upper and Lower Bound
Binary Search
Introduction
Binary search is a searching algorithm that finds the position of a target value within a sorted array. Compared to linear search, which checks each element one by one, binary search is far more efficient, reducing the time complexity from O(N) to O(log N).
In binary search, you start by looking at the middle element of the sorted array. If the middle element matches the target value, then you've found what you're looking for. If the target value is less than the middle element, then you search the left half of the array. If the target value is greater than the middle element, then you search the right half. You continue this process, halving the size of your search space at each step, until you either find the target value or confirm that it's not in the array.
Calculating Multiple Occurrences of an Element in an Array
Suppose you have a sorted array and you want to find how many times a particular element occurs in it. You can use a variation of the binary search algorithm to accomplish this task efficiently.
This method works efficiently because each binary search operation has a time complexity of O(log N).
But before attempting this question you must know about the Upper Bound and the Lower Bound in Binary Search.
Upper Bound and Lower Bound
These terms are often used in the context of binary search to find the "boundary" elements in a sorted array. Here’s what they mean:
Upper Bound
This is the smallest index where the value is greater than the given value. In simple terms, it's the first element that is strictly greater than the search value. Let’s see what will be the upper bound of 3 in given images.
Pseudo-Code for Upper Bound:
low = 0
high = length(arr) - 1
answer = -1
while (low <= high){
mid = (low + high) / 2
if (arr[mid] > target){
answer = mid
high = mid - 1
}
else{
low = mid + 1
}
}
return answer
Lower Bound:
This is the smallest index where the value is greater than or equal to the given value. In other words, it's the first element that is not smaller than the search value. Let’s see what will be the lower bound of 3 in the given images.
Pseudo-Code for Lower Bound:
low = 0
high = length(arr) - 1
answer = -1
while (low <= high){
mid = (low + high) / 2
if (arr[mid] >= target){
answer = mid
high = mid - 1
}
else{
low = mid + 1
}
}
return answer
Both upper bound and lower bound can be found using variations of the binary search algorithm and are particularly useful in range-based queries and searches.
Want to print your doc?
This is not the way.
This is not the way.
Try clicking the ⋯ next to your doc name or using a keyboard shortcut (
CtrlP
) instead.