Variants of Binary Search - Coding

Binary search is very easy right? Well, binary search can become complex when element duplication occurs in the sorted list of values. It’s not always the “contains or not” we search using Binary Search, but there are 5 variants such as below:
1) Contains (True or False)
2) Index of first occurrence of a key
3) Index of last occurrence of a key
4) Index of least element greater than key
5) Index of greatest element less than key

Each of these searches, while the base logic remains same, have a minor variation in implementation and competitive coders should be aware of them. You might have seen other approaches such as this for finding first and last occurrence, where you compare adjacent element also for checking of first/last element is reached.

From a complexity perspective, it may look like an O(log n) algorithm, but it doesn’t work when the comparisons itself are expensive. A problem to prove this point is linked at the end of this post, feel free to try it out.
Variant 1: Contains key (True or False)

Input : 2 3 3 5 5 5 6 6
Function : Contains(4)
Returns : False

Function : Contains(5)
Returns : True

Variant 2: First occurrence of key (index of array). This is similar to

C++

std::lower_bound(...)

Input : 2 3 3 5 5 5 6 6
Function : first(3)
Returns : 1

Function : first(5)
Returns : 3

Function : first(4)
Returns : -1

Variant 3: Last occurrence of key (index of array)

Input : 2 3 3 5 5 5 6 6
Function : last(3)
Returns : 2

Function : last(5)
Returns : 5

Function : last(4)
Returns : -1

Variant 4: index(first occurrence) of least integer greater than key. This is similar to

C++

std::upper_bound(...)

Input : 2 3 3 5 5 5 6 6
Function : leastGreater(2)
Returns : 1

Function : leastGreater(5)
Returns : 6

Variant 5: index(last occurrence) of greatest integer lesser than key

Input : 2 3 3 5 5 5 6 6
Function : greatestLesser(2)
Returns : -1

Function : greatestLesser(5)
Returns : 2

As you will see below, if you observe the clear difference between the implementations you will see that the same logic is used to find different variants of binary search.

C++

// C++ program to variants of Binary Search
#include <bits/stdc++.h>
 
using namespace std;
 
int n = 8; // array size
int a[] = { 2, 3, 3, 5, 5, 5, 6, 6 }; // Sorted array
 
/* Find if key is in array
 * Returns: True if key belongs to array,
 *          False if key doesn't belong to array */
bool contains(int low, int high, int key)
{
    bool ans = false;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int midVal = a[mid];
 
        if (midVal < key) {
 
            // if mid is less than key, all elements 
            // in range [low, mid] are also less
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
        else if (midVal > key) {
 
            // if mid is greater than key, all elements
            // in range [mid + 1, high] are also greater
            // so we now search in [low, mid - 1]
            high = mid - 1;
        }
        else if (midVal == key) {
 
            // comparison added just for the sake 
            // of clarity if mid is equal to key, we 
            // have found that key exists in array
            ans = true;
            break;
        }
    }
 
    return ans;
}
 
/* Find first occurrence index of key in array
 * Returns: an index in range [0, n-1] if key belongs 
 *          to array, -1 if key doesn't belong to array
 */
int first(int low, int high, int key)
{
    int ans = -1;
 
    while (low <= high) {
        int mid = low + (high - low + 1) / 2;
        int midVal = a[mid];
 
        if (midVal < key) {
 
            // if mid is less than key, all elements
            // in range [low, mid] are also less
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
        else if (midVal > key) {
 
            // if mid is greater than key, all elements 
            // in range [mid + 1, high] are also greater
            // so we now search in [low, mid - 1]
            high = mid - 1;
        }
        else if (midVal == key) {
 
            // if mid is equal to key, we note down
            //  the last found index then we search 
            // for more in left side of mid
            // so we now search in [low, mid - 1]
            ans = mid;
            high = mid - 1;
        }
    }
 
    return ans;
}
 
/* Find last occurrence index of key in array
 * Returns: an index in range [0, n-1] if key 
             belongs to array,
 *          -1 if key doesn't belong to array
 */
int last(int low, int high, int key)
{
    int ans = -1;
 
    while (low <= high) {
        int mid = low + (high - low + 1) / 2;
        int midVal = a[mid];
 
        if (midVal < key) {
 
            // if mid is less than key, then all elements 
            // in range [low, mid - 1] are also less
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
        else if (midVal > key) {
 
            // if mid is greater than key, then all 
            // elements in range [mid + 1, high] are 
            // also greater so we now search in 
            // [low, mid - 1]
            high = mid - 1;
        }
        else if (midVal == key) {
 
            // if mid is equal to key, we note down 
            // the last found index then we search 
            // for more in right side of mid
            // so we now search in [mid + 1, high]
            ans = mid;
            low = mid + 1;
        }
    }
 
    return ans;
}
 
/* Find index of first occurrence of least element 
   greater than key in array
 * Returns: an index in range [0, n-1] if key is not
             the greatest element in array,
 *          -1 if key is the greatest element in array */
int leastgreater(int low, int high, int key)
{
    int ans = -1;
 
    while (low <= high) {
        int mid = low + (high - low + 1) / 2;
        int midVal = a[mid];
 
        if (midVal < key) {
 
            // if mid is less than key, all elements
            // in range [low, mid - 1] are <= key
            // then we search in right side of mid
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
        else if (midVal > key) {
 
            // if mid is greater than key, all elements
            // in range [mid + 1, high] are >= key
            // we note down the last found index, then 
            // we search in left side of mid
            // so we now search in [low, mid - 1]
            ans = mid;
            high = mid - 1;
        }
        else if (midVal == key) {
 
            // if mid is equal to key, all elements in
            // range [low, mid] are <= key
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
    }
 
    return ans;
}
 
/* Find index of last occurrence of greatest element
   less than key in array
 * Returns: an index in range [0, n-1] if key is not 
             the least element in array,
 *          -1 if key is the least element in array */
int greatestlesser(int low, int high, int key)
{
    int ans = -1;
 
    while (low <= high) {
        int mid = low + (high - low + 1) / 2;
        int midVal = a[mid];
 
        if (midVal < key) {
 
            // if mid is less than key, all elements 
            // in range [low, mid - 1] are < key
            // we note down the last found index, then 
            // we search in right side of mid
            // so we now search in [mid + 1, high]
            ans = mid;
            low = mid + 1;
        }
        else if (midVal > key) {
 
            // if mid is greater than key, all elements
            // in range [mid + 1, high] are > key
            // then we search in left side of mid
            // so we now search in [low, mid - 1]
            high = mid - 1;
        }
        else if (midVal == key) {
 
            // if mid is equal to key, all elements 
            // in range [mid + 1, high] are >= key
            // then we search in left side of mid
            // so we now search in [low, mid - 1]
            high = mid - 1;
        }
    }
 
    return ans;
}
 
int main()
{
    printf("Contains\n");
    for (int i = 0; i < 10; i++)
        printf("%d %d\n", i, contains(0, n - 1, i));
 
    printf("First occurrence of key\n");
    for (int i = 0; i < 10; i++)
        printf("%d %d\n", i, first(0, n - 1, i));
 
    printf("Last occurrence of key\n");
    for (int i = 0; i < 10; i++)
        printf("%d %d\n", i, last(0, n - 1, i));
 
    printf("Least integer greater than key\n");
    for (int i = 0; i < 10; i++)
        printf("%d %d\n", i, leastgreater(0, n - 1, i));
 
    printf("Greatest integer lesser than key\n");
    for (int i = 0; i < 10; i++)
        printf("%d %d\n", i, greatestlesser(0, n - 1, i));
 
    return 0;
}

Java

// Java program to variants of Binary Search
import java.util.*;
 
class GFG{
     
// Array size    
static int n = 8; 
  
// Sorted array
static int a[] = { 2, 3, 3, 5, 5, 5, 6, 6 };
   
/* Find if key is in array
 * Returns: True if key belongs to array,
 * False if key doesn't belong to array */
static int contains(int low, int high, int key)
{
    int ans = 0;
     
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        int midVal = a[mid];
   
        if (midVal < key)
        {
             
            // If mid is less than key, all elements 
            // in range [low, mid] are also less
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
        else if (midVal > key)
        {
              
            // If mid is greater than key, all elements
            // in range [mid + 1, high] are also greater
            // so we now search in [low, mid - 1]
            high = mid - 1;
        }
        else if (midVal == key)
        {
              
            // Comparison added just for the sake 
            // of clarity if mid is equal to key, we 
            // have found that key exists in array
            ans = 1;
            break;
        }
    }
    return ans;
}
   
/* Find first occurrence index of key in array
 * Returns: an index in range [0, n-1] if key belongs 
 *          to array, -1 if key doesn't belong to array
 */
static int first(int low, int high, int key)
{
    int ans = -1;
   
    while (low <= high) 
    {
        int mid = low + (high - low + 1) / 2;
        int midVal = a[mid];
   
        if (midVal < key) 
        {
             
            // If mid is less than key, all elements
            // in range [low, mid] are also less
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
        else if (midVal > key)
        {
              
            // If mid is greater than key, all elements 
            // in range [mid + 1, high] are also greater
            // so we now search in [low, mid - 1]
            high = mid - 1;
        }
        else if (midVal == key)
        {
              
            // If mid is equal to key, we note down
            //  the last found index then we search 
            // for more in left side of mid
            // so we now search in [low, mid - 1]
            ans = mid;
            high = mid - 1;
        }
    }
    return ans;
}
   
/* Find last occurrence index of key in array
 * Returns: an index in range [0, n-1] if key 
            belongs to array, -1 if key doesn't
            belong to array
 */
static int last(int low, int high, int key)
{
    int ans = -1;
   
    while (low <= high)
    {
        int mid = low + (high - low + 1) / 2;
        int midVal = a[mid];
   
        if (midVal < key) 
        {
             
            // If mid is less than key, then all elements 
            // in range [low, mid - 1] are also less
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
        else if (midVal > key)
        {
              
            // If mid is greater than key, then all 
            // elements in range [mid + 1, high] are 
            // also greater so we now search in 
            // [low, mid - 1]
            high = mid - 1;
        }
        else if (midVal == key) 
        {
              
            // If mid is equal to key, we note down 
            // the last found index then we search 
            // for more in right side of mid
            // so we now search in [mid + 1, high]
            ans = mid;
            low = mid + 1;
        }
    }
    return ans;
}
   
/* Find index of first occurrence of least element 
   greater than key in array
 * Returns: an index in range [0, n-1] if key is not
            the greatest element in array, -1 if key
 *          is the greatest element in array */
static int leastgreater(int low, int high, int key)
{
    int ans = -1;
   
    while (low <= high) 
    {
        int mid = low + (high - low + 1) / 2;
        int midVal = a[mid];
   
        if (midVal < key) 
        {
             
            // If mid is less than key, all elements
            // in range [low, mid - 1] are <= key
            // then we search in right side of mid
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
        else if (midVal > key)
        {
              
            // If mid is greater than key, all elements
            // in range [mid + 1, high] are >= key
            // we note down the last found index, then 
            // we search in left side of mid
            // so we now search in [low, mid - 1]
            ans = mid;
            high = mid - 1;
        }
        else if (midVal == key)
        {
              
            // If mid is equal to key, all elements in
            // range [low, mid] are <= key
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
    }
    return ans;
}
   
/* Find index of last occurrence of greatest element
   less than key in array
 * Returns: an index in range [0, n-1] if key is not 
            the least element in array, -1 if 
 *          key is the least element in array */
static int greatestlesser(int low, int high, int key)
{
    int ans = -1;
   
    while (low <= high)
    {
        int mid = low + (high - low + 1) / 2;
        int midVal = a[mid];
   
        if (midVal < key)
        {
              
            // If mid is less than key, all elements 
            // in range [low, mid - 1] are < key
            // we note down the last found index, then 
            // we search in right side of mid
            // so we now search in [mid + 1, high]
            ans = mid;
            low = mid + 1;
        }
        else if (midVal > key) 
        {
              
            // If mid is greater than key, all elements
            // in range [mid + 1, high] are > key
            // then we search in left side of mid
            // so we now search in [low, mid - 1]
            high = mid - 1;
        }
        else if (midVal == key)
        {
              
            // If mid is equal to key, all elements 
            // in range [mid + 1, high] are >= key
            // then we search in left side of mid
            // so we now search in [low, mid - 1]
            high = mid - 1;
        }
    }
   
    return ans;
}  
 
// Driver Code
public static void main(String[] args)
{
    System.out.println("Contains");
    for(int i = 0; i < 10; i++)
        System.out.println(i + " " + contains(0, n - 1, i));
      
    System.out.println("First occurrence of key");
    for(int i = 0; i < 10; i++)
        System.out.println(i + " " + first(0, n - 1, i));
      
    System.out.println("Last occurrence of key");
    for(int i = 0; i < 10; i++)
        System.out.println(i + " " + last(0, n - 1, i));
      
    System.out.println("Least integer greater than key");
    for(int i = 0; i < 10; i++)
        System.out.println(i + " " + 
                           leastgreater(0, n - 1, i));
      
    System.out.println("Greatest integer lesser than key");
    for(int i = 0; i < 10; i++)
        System.out.println(i + " " + 
                           greatestlesser(0, n - 1, i));
}
}
 
// This code is contributed by divyeshrabadiya07

Python3

# Python3 program to variants of Binary Search
 
n = 8;      # array size
a = [ 2, 3, 3, 5, 5, 5, 6, 6 ];     # Sorted array
 
# Find if key is in array
# Returns: True if key belongs to array,
# False if key doesn't belong to array 
def contains(low, high, key):
    ans = False;
    while (low <= high):
        mid = low + ((high - low) // 2);
        midVal = a[mid];
 
        if (midVal < key): 
 
            # if mid is less than key, all elements 
            # in range [low, mid] are also less
            # so we now search in [mid + 1, high]
            low = mid + 1;
         
        elif (midVal > key):
 
            # if mid is greater than key, all elements
            # in range [mid + 1, high] are also greater
            # so we now search in [low, mid - 1]
            high = mid - 1;
         
        elif (midVal == key):
 
            # comparison added just for the sake 
            # of clarity if mid is equal to key, we 
            # have found that key exists in array
            ans = True;
            break;
         
    return ans;
 
 
# Find first occurrence index of key in array
# Returns: an index in range [0, n-1] if key belongs 
#          to array, -1 if key doesn't belong to array
 
def first(low, high, key):
     
    ans = -1;
 
    while (low <= high):
        mid = low + ((high - low + 1) // 2);
        midVal = a[mid];
 
        if (midVal < key):
 
            # if mid is less than key, all elements
            # in range [low, mid] are also less
            # so we now search in [mid + 1, high]
            low = mid + 1;
         
        elif (midVal > key):
 
            # if mid is greater than key, all elements 
            # in range [mid + 1, high] are also greater
            # so we now search in [low, mid - 1]
            high = mid - 1;
         
        elif (midVal == key):
 
            # if mid is equal to key, we note down
            #  the last found index then we search 
            # for more in left side of mid
            # so we now search in [low, mid - 1]
            ans = mid;
            high = mid - 1;
 
    return ans;
 
 
# Find last occurrence index of key in array
# Returns: an index in range [0, n-1] if key 
# belongs to array,
#          -1 if key doesn't belong to array
 
def last(low, high, key):
    ans = -1;
 
    while (low <= high):
        mid = low + ((high - low + 1) // 2);
        midVal = a[mid];
 
        if (midVal < key):
 
            # if mid is less than key, then all elements 
            # in range [low, mid - 1] are also less
            # so we now search in [mid + 1, high]
            low = mid + 1;
         
        elif (midVal > key):
 
            # if mid is greater than key, then all 
            # elements in range [mid + 1, high] are 
            # also greater so we now search in 
            # [low, mid - 1]
            high = mid - 1;
         
        elif (midVal == key):
 
            # if mid is equal to key, we note down 
            # the last found index then we search 
            # for more in right side of mid
            # so we now search in [mid + 1, high]
            ans = mid;
            low = mid + 1;
     
    return ans;
 
 
# Find index of first occurrence of least element 
# greater than key in array
# Returns: an index in range [0, n-1] if key is not
# the greatest element in array,
# -1 if key is the greatest element in array */
def leastgreater(low, high, key):
    ans = -1;
 
    while (low <= high):
        mid = low + ((high - low + 1) // 2);
        midVal = a[mid];
 
        if (midVal < key):
 
            # if mid is less than key, all elements
            # in range [low, mid - 1] are <= key
            # then we search in right side of mid
            # so we now search in [mid + 1, high]
            low = mid + 1;
         
        elif (midVal > key) :
 
            # if mid is greater than key, all elements
            # in range [mid + 1, high] are >= key
            # we note down the last found index, then 
            # we search in left side of mid
            # so we now search in [low, mid - 1]
            ans = mid;
            high = mid - 1;
         
        elif (midVal == key) :
 
            # if mid is equal to key, all elements in
            # range [low, mid] are <= key
            # so we now search in [mid + 1, high]
            low = mid + 1;
 
    return ans;
 
 
# Find index of last occurrence of greatest element
# less than key in array
# Returns: an index in range [0, n-1] if key is not 
# the least element in array,
# -1 if key is the least element in array */
def greatestlesser(low, high, key):
    ans = -1;
 
    while (low <= high):
        mid = low + ((high - low + 1) // 2);
        midVal = a[mid];
 
        if (midVal < key):
 
            # if mid is less than key, all elements 
            # in range [low, mid - 1] are < key
            # we note down the last found index, then 
            # we search in right side of mid
            # so we now search in [mid + 1, high]
            ans = mid;
            low = mid + 1;
         
        elif (midVal > key):
 
            # if mid is greater than key, all elements
            # in range [mid + 1, high] are > key
            # then we search in left side of mid
            # so we now search in [low, mid - 1]
            high = mid - 1;
         
        elif (midVal == key) :
 
            # if mid is equal to key, all elements 
            # in range [mid + 1, high] are >= key
            # then we search in left side of mid
            # so we now search in [low, mid - 1]
            high = mid - 1;
         
    return ans;
 
 
print("Contains");
 
for i in range(10):
    print(i, contains(0, n - 1, i));
 
print("First occurrence of key");
for i in range(10):
    print(i, first(0, n - 1, i));
 
print("Last occurrence of key");
for i in range(10):
    print(i, last(0, n - 1, i));
 
 
print("Least integer greater than key");
for i in range(10):
    print(i, leastgreater(0, n - 1, i));
 
 
print("Greatest integer lesser than key");
for i in range(10):
    print(i, greatestlesser(0, n - 1, i));
 
 
 
# This code is contributed by phasing17

C#

// C# program to variants of Binary Search
using System;
 
class GFG{
     
// Array size    
static int n = 8; 
 
// Sorted array
static int[] a = { 2, 3, 3, 5, 5, 5, 6, 6 };
  
/* Find if key is in array
 * Returns: True if key belongs to array,
 * False if key doesn't belong to array */
static int contains(int low, int high, int key)
{
    int ans = 0;
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        int midVal = a[mid];
  
        if (midVal < key)
        {
             
            // If mid is less than key, all elements 
            // in range [low, mid] are also less
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
        else if (midVal > key)
        {
             
            // If mid is greater than key, all elements
            // in range [mid + 1, high] are also greater
            // so we now search in [low, mid - 1]
            high = mid - 1;
        }
        else if (midVal == key)
        {
             
            // Comparison added just for the sake 
            // of clarity if mid is equal to key, we 
            // have found that key exists in array
            ans = 1;
            break;
        }
    }
    return ans;
}
  
/* Find first occurrence index of key in array
 * Returns: an index in range [0, n-1] if key belongs 
 *          to array, -1 if key doesn't belong to array
 */
static int first(int low, int high, int key)
{
    int ans = -1;
  
    while (low <= high) 
    {
        int mid = low + (high - low + 1) / 2;
        int midVal = a[mid];
  
        if (midVal < key) 
        {
             
            // If mid is less than key, all elements
            // in range [low, mid] are also less
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
        else if (midVal > key)
        {
             
            // If mid is greater than key, all elements 
            // in range [mid + 1, high] are also greater
            // so we now search in [low, mid - 1]
            high = mid - 1;
        }
        else if (midVal == key)
        {
             
            // If mid is equal to key, we note down
            //  the last found index then we search 
            // for more in left side of mid
            // so we now search in [low, mid - 1]
            ans = mid;
            high = mid - 1;
        }
    }
    return ans;
}
  
/* Find last occurrence index of key in array
 * Returns: an index in range [0, n-1] if key 
             belongs to array, -1 if key doesn't
             belong to array
 */
static int last(int low, int high, int key)
{
    int ans = -1;
  
    while (low <= high)
    {
        int mid = low + (high - low + 1) / 2;
        int midVal = a[mid];
  
        if (midVal < key) 
        {
             
            // If mid is less than key, then all elements 
            // in range [low, mid - 1] are also less
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
        else if (midVal > key)
        {
             
            // If mid is greater than key, then all 
            // elements in range [mid + 1, high] are 
            // also greater so we now search in 
            // [low, mid - 1]
            high = mid - 1;
        }
        else if (midVal == key) 
        {
             
            // If mid is equal to key, we note down 
            // the last found index then we search 
            // for more in right side of mid
            // so we now search in [mid + 1, high]
            ans = mid;
            low = mid + 1;
        }
    }
    return ans;
}
  
/* Find index of first occurrence of least element 
   greater than key in array
 * Returns: an index in range [0, n-1] if key is not
             the greatest element in array,
 *          -1 if key is the greatest element in array */
static int leastgreater(int low, int high, int key)
{
    int ans = -1;
  
    while (low <= high) 
    {
        int mid = low + (high - low + 1) / 2;
        int midVal = a[mid];
  
        if (midVal < key) 
        {
             
            // If mid is less than key, all elements
            // in range [low, mid - 1] are <= key
            // then we search in right side of mid
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
        else if (midVal > key)
        {
             
            // If mid is greater than key, all elements
            // in range [mid + 1, high] are >= key
            // we note down the last found index, then 
            // we search in left side of mid
            // so we now search in [low, mid - 1]
            ans = mid;
            high = mid - 1;
        }
        else if (midVal == key)
        {
             
            // If mid is equal to key, all elements in
            // range [low, mid] are <= key
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
    }
    return ans;
}
  
/* Find index of last occurrence of greatest element
   less than key in array
 * Returns: an index in range [0, n-1] if key is not 
             the least element in array,
 *          -1 if key is the least element in array */
static int greatestlesser(int low, int high, int key)
{
    int ans = -1;
  
    while (low <= high)
    {
        int mid = low + (high - low + 1) / 2;
        int midVal = a[mid];
  
        if (midVal < key)
        {
             
            // If mid is less than key, all elements 
            // in range [low, mid - 1] are < key
            // we note down the last found index, then 
            // we search in right side of mid
            // so we now search in [mid + 1, high]
            ans = mid;
            low = mid + 1;
        }
        else if (midVal > key) 
        {
             
            // If mid is greater than key, all elements
            // in range [mid + 1, high] are > key
            // then we search in left side of mid
            // so we now search in [low, mid - 1]
            high = mid - 1;
        }
        else if (midVal == key)
        {
             
            // If mid is equal to key, all elements 
            // in range [mid + 1, high] are >= key
            // then we search in left side of mid
            // so we now search in [low, mid - 1]
            high = mid - 1;
        }
    }
  
    return ans;
} 
 
// Driver Code
static void Main() 
{
    Console.WriteLine("Contains");
    for(int i = 0; i < 10; i++)
        Console.WriteLine(i + " " + contains(0, n - 1, i));
     
    Console.WriteLine("First occurrence of key");
    for(int i = 0; i < 10; i++)
        Console.WriteLine(i + " " + first(0, n - 1, i));
     
    Console.WriteLine("Last occurrence of key");
    for(int i = 0; i < 10; i++)
        Console.WriteLine(i + " " + last(0, n - 1, i));
     
    Console.WriteLine("Least integer greater than key");
    for(int i = 0; i < 10; i++)
        Console.WriteLine(i + " " + 
                          leastgreater(0, n - 1, i));
     
    Console.WriteLine("Greatest integer lesser than key");
    for(int i = 0; i < 10; i++)
        Console.WriteLine(i + " " +
                          greatestlesser(0, n - 1, i));
}
}
 
// This code is contributed by divyesh072019

Javascript

// JavaScript program to variants of Binary Search
 
 
let n = 8; // array size
let a = [ 2, 3, 3, 5, 5, 5, 6, 6 ]; // Sorted array
 
/* Find if key is in array
 * Returns: True if key belongs to array,
 *          False if key doesn't belong to array */
function contains(low, high, key)
{
    let ans = false;
    while (low <= high) {
        let mid = low + Math.floor((high - low) / 2);
        let midVal = a[mid];
 
        if (midVal < key) {
 
            // if mid is less than key, all elements 
            // in range [low, mid] are also less
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
        else if (midVal > key) {
 
            // if mid is greater than key, all elements
            // in range [mid + 1, high] are also greater
            // so we now search in [low, mid - 1]
            high = mid - 1;
        }
        else if (midVal == key) {
 
            // comparison added just for the sake 
            // of clarity if mid is equal to key, we 
            // have found that key exists in array
            ans = true;
            break;
        }
    }
 
    return ans;
}
 
/* Find first occurrence index of key in array
 * Returns: an index in range [0, n-1] if key belongs 
 *          to array, -1 if key doesn't belong to array
 */
function first(low, high, key)
{
    let ans = -1;
 
    while (low <= high) {
        let mid = low + Math.floor((high - low + 1) / 2);
        let midVal = a[mid];
 
        if (midVal < key) {
 
            // if mid is less than key, all elements
            // in range [low, mid] are also less
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
        else if (midVal > key) {
 
            // if mid is greater than key, all elements 
            // in range [mid + 1, high] are also greater
            // so we now search in [low, mid - 1]
            high = mid - 1;
        }
        else if (midVal == key) {
 
            // if mid is equal to key, we note down
            //  the last found index then we search 
            // for more in left side of mid
            // so we now search in [low, mid - 1]
            ans = mid;
            high = mid - 1;
        }
    }
 
    return ans;
}
 
/* Find last occurrence index of key in array
 * Returns: an index in range [0, n-1] if key 
             belongs to array,
 *          -1 if key doesn't belong to array
 */
function last(low, high, key)
{
    let ans = -1;
 
    while (low <= high) {
        let mid = low + Math.floor((high - low + 1) / 2);
        let midVal = a[mid];
 
        if (midVal < key) {
 
            // if mid is less than key, then all elements 
            // in range [low, mid - 1] are also less
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
        else if (midVal > key) {
 
            // if mid is greater than key, then all 
            // elements in range [mid + 1, high] are 
            // also greater so we now search in 
            // [low, mid - 1]
            high = mid - 1;
        }
        else if (midVal == key) {
 
            // if mid is equal to key, we note down 
            // the last found index then we search 
            // for more in right side of mid
            // so we now search in [mid + 1, high]
            ans = mid;
            low = mid + 1;
        }
    }
 
    return ans;
}
 
/* Find index of first occurrence of least element 
   greater than key in array
 * Returns: an index in range [0, n-1] if key is not
             the greatest element in array,
 *          -1 if key is the greatest element in array */
function leastgreater(low, high, key)
{
    let ans = -1;
 
    while (low <= high) {
        let mid = low + Math.floor((high - low + 1) / 2);
        let midVal = a[mid];
 
        if (midVal < key) {
 
            // if mid is less than key, all elements
            // in range [low, mid - 1] are <= key
            // then we search in right side of mid
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
        else if (midVal > key) {
 
            // if mid is greater than key, all elements
            // in range [mid + 1, high] are >= key
            // we note down the last found index, then 
            // we search in left side of mid
            // so we now search in [low, mid - 1]
            ans = mid;
            high = mid - 1;
        }
        else if (midVal == key) {
 
            // if mid is equal to key, all elements in
            // range [low, mid] are <= key
            // so we now search in [mid + 1, high]
            low = mid + 1;
        }
    }
 
    return ans;
}
 
/* Find index of last occurrence of greatest element
   less than key in array
 * Returns: an index in range [0, n-1] if key is not 
             the least element in array,
 *          -1 if key is the least element in array */
function greatestlesser(low, high, key)
{
    let ans = -1;
 
    while (low <= high) {
        let mid = low + Math.floor((high - low + 1) / 2);
        let midVal = a[mid];
 
        if (midVal < key) {
 
            // if mid is less than key, all elements 
            // in range [low, mid - 1] are < key
            // we note down the last found index, then 
            // we search in right side of mid
            // so we now search in [mid + 1, high]
            ans = mid;
            low = mid + 1;
        }
        else if (midVal > key) {
 
            // if mid is greater than key, all elements
            // in range [mid + 1, high] are > key
            // then we search in left side of mid
            // so we now search in [low, mid - 1]
            high = mid - 1;
        }
        else if (midVal == key) {
 
            // if mid is equal to key, all elements 
            // in range [mid + 1, high] are >= key
            // then we search in left side of mid
            // so we now search in [low, mid - 1]
            high = mid - 1;
        }
    }
 
    return ans;
}
 
console.log("Contains");
 
for (var i = 0; i < 10; i++)
    console.log(i, contains(0, n - 1, i));
 
console.log("First occurrence of key");
for (var i = 0; i < 10; i++)
    console.log(i, first(0, n - 1, i));
 
console.log("Last occurrence of key");
for (var i = 0; i < 10; i++)
    console.log(i, last(0, n - 1, i));
 
console.log("Least integer greater than key");
for (var i = 0; i < 10; i++)
    console.log(i, leastgreater(0, n - 1, i));
 
console.log("Greatest integer lesser than key");
for (var i = 0; i < 10; i++)
    console.log(i, greatestlesser(0, n - 1, i));
 
 
 
// This code is contributed by phasing17

Output:

Contains
0 0
1 0
2 1
3 1
4 0
5 1
6 1
7 0
8 0
9 0
First occurrence of key
0 -1
1 -1
2 0
3 1
4 -1
5 3
6 6
7 -1
8 -1
9 -1
Last occurrence of key
0 -1
1 -1
2 0
3 2
4 -1
5 5
6 7
7 -1
8 -1
9 -1
Least integer greater than key
0 0
1 0
2 1
3 3
4 3
5 6
6 -1
7 -1
8 -1
9 -1
Greatest integer lesser than key
0 -1
1 -1
2 -1
3 0
4 2
5 2
6 5
7 7
8 7
9 7

Here is the problem I have mentioned at the beginning of the post: KCOMPRES problem in Codechef. Do try it out and feel free post your queries here.
More Binary Search Practice Problems

Elevate your coding journey with a Premium subscription. Benefit from ad-free learning, unlimited article summaries, an AI bot, access to 35+ courses, and more-available only with GeeksforGeeks Premium! Explore now!

Reffered: https://www.geeksforgeeks.org

Searching

Related
Longest Subarray with first element greater than or equal to Last element
Largest subarray having sum greater than k
Find the only missing number in a sorted array
Ways to choose three points with distance between the most distant points <= L
Maximum adjacent difference in an array in its sorted form

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	11