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:

  1. Finding the first occurrence of the searching key
  2. Finding the last occurrence of the searching key
  3. Finding the least possible element greater than the key
  4. 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(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.  

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





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.