# Variants of Binary Search

**Variants of Binary Search**: In this article, we have explained four different use cases where the variation of binary search has been used.

Submitted by Radib Kar, on July 23, 2020

**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.

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.

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,

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)

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).

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,

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)

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**

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.

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**.

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

**2) Finding the greatest possible element less than the key**

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.

Now there can be edge cases, like the first occurrence can be the first element(0^{th} 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**.

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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions