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

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

Related Tutorials

- Introduction to Algorithms
- Introduction to Greedy Strategy in Algorithms
- Stability in sorting
- External Merge Sorting Algorithm
- Radix Sort and its Algorithm
- Bucket Sort Algorithm
- Bubble sort Algorithm, Flow Chart and C++ Code
- Insertion sort Algorithm, flowchart and C, C++ Code
- Merge Sort | One of the best sorting algorithms used for large inputs
- Binary Search in C, C++
- Randomized Binary Search
- Meta Binary Search | One-sided Binary Search
- Difference between Linear Search and Binary Search
- Binary Search in String
- Sieve of Eratosthenes to find prime numbers
- Optimal Merge Pattern (Algorithm and Example)
- Given an array of n numbers, Check whether there is any duplicate or not
- Finding the missing number
- Find the number occurring an odd number of times
- Find the pair whose sum is closest to zero in minimum time complexity
- Find three elements in an array such that their sum is equal to given element K
- Bitonic Search Algorithm
- Check whether a number is Fibonacci or not
- Segregate even and odd numbers in minimum time complexity
- Find trailing zeros in factorial of a number
- Find Nearest Greatest Neighbours of each element in an array
- Interpolation search algorithm
- Floor and ceil of an element in an array using C++
- Two Elements whose sum is closest to zero
- Find a pair with a given difference
- Count number of occurrences (or frequency) in a sorted array
- Find a Fixed Point (Value equal to index) in a given array
- Find the maximum element in an array which is first increasing and then decreasing
- Dynamic Programming (Components, Applications and Elements)
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Dynamic Programming (Components, Applications and Elements)
- Find the Nth Fibonacci number | C++
- Longest Common Subsequence using Dynamic programming (DP)
- Longest Increasing Subsequence using Dynamic programming (DP)
- Find the maximum sub-array sum using KADANE'S ALGORITHM
- Non-intersecting chords using Dynamic Programming (DP)
- Edit Distance using Dynamic Programming (DP)
- Finding Ugly Number using Dynamic Programming (DP)
- Egg dropping problem using Dynamic Programming (DP)
- Wild card matching problem using Dynamic programming (DP)
- Compute sum of digits in all numbers from 1 to N for a given N
- Minimum jumps required using Dynamic programming (DP)
- Graph coloring problem's solution using backtracking algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- Travelling Salesman Problem
- Kruskal's (P) and Prim's (K) Algorithms
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code

- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Find the GCD (Greatest Common Divisor) of two numbers using EUCLID'S ALGORITHM
- Compute the value of A raise to the power B using Fast Exponentiation
- Implement First Come First Served (FCFS) CPU Scheduling Algorithm using C program
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Analysis of LRU page replacement algorithm and Belady's anomaly
- Branch and Bound
- Find the roots of a complex polynomial equation using Regula Falsi Method in C
- Sieve of Eratosthenes to find prime numbers
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Divide and Conquer Paradigm (What it is, Its Applications, Pros and Cons)
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Jump Search Implementation using C++
- Optimal Merge Pattern (Algorithm and Example)
- Introduction to Greedy Strategy in Algorithms
- Strassen's Matrix Multiplication in algorithms
- Huffman Coding (Algorithm, Example and Time complexity)
- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Graph coloring problem's solution using backtracking algorithm
- Tournament Tree and their properties
- Deterministic and Non Deterministic Algorithms
- Lower Bound Theory
- Non Recursive Tree Traversal Algorithm
- Line Drawing Algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- P and NP problems and solutions | Algorithms
- Travelling Salesman Problem
- 2 – 3 Trees Algorithm
- Kruskal's (P) and Prim's (K) Algorithms
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Midpoint Circle Algorithm
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code
- Reliability design problem
- Removing consecutive duplicates from a string
- Fast Exponentiation using Bitmasking

Comments and Discussions!