Home »
Algorithms
Variants of Binary Search
Variants of Binary Search: In this tutorial, we will learn about the four different use cases where the variation of binary search is used.
By Radib Kar Last updated : August 16, 2023
Prerequisite
Binary search is one of the popular searching algorithms in is often preferred if the input list is sorted. In general, it's easy to implement, but there are several use cases where binary search can be used efficiently.
Different Variants of Binary Search
The use cases where variants of binary search are used are below:
- Finding the first occurrence of the searching key
- Finding the last occurrence of the searching key
- Finding the least possible element greater than the key
- Finding the greatest possible element less than the key
1. Finding the first occurrence of the searching key
In the sorted input list, the searching key may have more than one more occurrence. In that case, we need to find the first occurrence of searching key using binary search. The idea would remain the same, the only difference would be not stopping when we find the search key. Instead of terminating, we would continue to search again in the left half so that if there is more occurrence in the left, it will be able to find the leftmost.
Example
For example, say the input is [4, 5, 6, 6, 6, 7, 8, 9] and say the searching key is 6
Here at the first iteration,
Solution
We find mid is 4 and array[mid] is 6. If we followed a general binary search we would have stopped and terminated the execution. But here as we need to find the first most(leftmost) occurrence, we would continue to search in the left half by keeping track of the already found index. If the search key is not available in the left half, then the program will terminate and the stored index (that we tracked) would be the result. Otherwise, if the key is there in the left half it will continue to search and eventually find the leftmost occurrence.
In the above input, the first occurrence of the search key, 6 is 2(index)
C++ Implementation
Below is the implementation:
#include <bits/stdc++.h>
using namespace std;
int find_first_occurrence(vector<int> arr, int key)
{
int left = 0, right = arr.size() - 1;
int index = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
// store mid as found index and
// continue search in the left
if (arr[mid] == key) {
index = mid;
right = mid - 1;
}
else if (arr[mid] > key) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return index;
}
int main()
{
vector<int> arr{ 4, 5, 6, 6, 6, 7, 8 };
int key = 6;
int index = find_first_occurrence(arr, key);
if (index != -1)
cout << "The first occurrence of key " << key << " is at: " << index << endl;
else
cout << "Key not found\n";
return 0;
}
Output
The first occurrence of key 6 is at: 2
2. Finding the last occurrence of the searching key
Now, there may be the case, that we require the last occurrence. The idea is similar to finding the first occurrence, but here instead of terminating, we would continue to search again in the right half so that if there is more occurrence in the right, it will be able to find the rightmost (last occurrence).
Example
For example say the input is [4, 5, 6, 6, 6, 7, 8, 9] and say the searching key is 6
Here at the first iteration,
Solution
We find mid is 4 and array[mid] is 6. If we followed a general binary search we would have stopped and terminated the execution. But here as we need to find the last (rightmost) occurrence, we would continue to search in the right half by keeping track of the already found index. If the search key is not available in the right half, then the program will terminate and the stored index (that we tracked) would be the result. Otherwise, if the key is there in the right half, then it will continue to search and eventually find the rightmost (last) occurrence. In the above input, the last occurrence of the search key, 6 is 4(index).
C++ Implementation
Below is the implementation:
#include <bits/stdc++.h>
using namespace std;
int find_last_occurrence(vector<int> arr, int key)
{
int left = 0, right = arr.size() - 1;
int index = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
// continue search in right half
if (arr[mid] == key) {
index = mid;
left = mid + 1;
}
else if (arr[mid] > key) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return index;
}
int main()
{
vector<int> arr{ 4, 5, 6, 6, 6, 7, 8 };
int key = 6;
int index = find_last_occurrence(arr, key);
if (index != -1)
cout << "The last occurrence of key " << key << " is at: " << index << endl;
else
cout << "Key not found\n";
return 0;
}
Output
The last occurrence of key 6 is at: 4
3. Finding the least possible element greater than the key
Example
Again we will bring the above example. So, the sorted list is: [4, 5, 6, 6, 6, 7, 8, 9] and the searching key is 6. So obviously the least element greater than the key is 7. What is 7? It's the next immediate element of the last occurrence of the searching key.
Solution
Now there can be edge cases, like the last occurrence can be the last element which means for the searching key no greater key exists. If the last occurrence is not the last element then the least greater element will be the next immediate right element of the last occurrence.
C++ Implementation
Below is the implementation:
#include <bits/stdc++.h>
using namespace std;
//finding last occurrence of the key
int find_last_occurrence(vector<int> arr, int key)
{
int left = 0, right = arr.size() - 1;
int index = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
//continue search in right half
if (arr[mid] == key) {
index = mid;
left = mid + 1;
} //rest is normal binary search
else if (arr[mid] > key) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return index;
}
int main()
{
vector<int> arr{ 4, 5, 6, 6, 6, 7, 8 };
int key = 6;
int index = find_last_occurrence(arr, key);
if (index != -1 && index != arr.size() - 1)
cout << "The least greater element for key " << key << " is: " << arr[index + 1] << endl;
else //either last occurrence is the extreme element or key not found
cout << "No least greater element is possible for the key\n";
return 0;
}
Output
The least greater element for key 6 is: 7
4. Finding the greatest possible element less than the key
Example
Again we will bring the above example. So, the sorted list is: [4, 5, 6, 6, 6, 7, 8, 9] and the searching key is 6. So obviously the greatest element less than the key is 5. What is 5? It's the immediate previous element of the first occurrence of the searching key.
Solution
Now there can be edge cases, like the first occurrence can be the first element(0th element) which means for the searching key no lesser key exists. If the first occurrence of the search key is not the first element then the greatest less element will be an immediate previous(left) element of the first occurrence of the search key.
C++ Implementation
Below is the implementation:
#include <bits/stdc++.h>
using namespace std;
//finding first occurrence
int find_first_occurrence(vector<int> arr, int key)
{
int left = 0, right = arr.size() - 1;
int index = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
//store mid as found index and
//continue search in the left
if (arr[mid] == key) {
index = mid;
right = mid - 1;
}
else if (arr[mid] > key) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return index;
}
int main()
{
vector<int> arr{ 4, 5, 6, 6, 6, 7, 8 };
int key = 6;
int index = find_first_occurrence(arr, key);
//key is found & first occurrence is not the first element
if (index != -1 && index != 0)
cout << "The greatest lesser element of key " << key << " is : " << arr[index - 1] << endl;
else //either first occurrence is the first element or key not found
cout << "The greatest lesser element for the key is possible\n";
return 0;
}
Output
The greatest lesser element of key 6 is : 5