Many a times we face the need to modify binary search for solving different Competitive Coding problems. I am archiving some of the most used variations of Binary Search:

• Normal Binary search with two comparisons:

```int BinarySearch(int A[], int l, int r, int key)
{
int m;
while( l <= r )
{
m = l + (r-l)/2;

if( A[m] == key ) // first comparison
return m;

if( A[m] < key ) // second comparison
l = m + 1;
else
r = m - 1;
}
return -1;
}```
• Binary Search with less comarisons:

```// Input: A[l .... r-1]
// Note A[r] is not being searched
int BinarySearch(int A[], int l, int r, int key)
{
int m;
while( r - l > 1 )
{
m = l + (r-l)/2;

if( A[m] <= key )
l = m;
else
r = m;
}

if( A[l] == key )
return l;
else
return -1;
}
```
• Binary search used to find the floor value in code:
Note: If there are duplicates, this will return the index of the last occurrence of key.

```//  Eg.The code will return 3 if searched for 4
//  in array [1,2,3,5,6]
//  Input: A[l .... r-1]
//  Note A[r] is not being searched
int Floor(int A[], int l, int r, int key)
{
int m;
while( r - l > 1 )
{
m = l + (r - l)/2;
if( A[m] <= key )
l = m;
else
r = m;
}
return A[l];
}

// Initial call
int Floor(int A[], int size, int key)
{
// Add error checking if key < A[0]
if( key < A[0] )
return -1;
// Observe boundaries
return Floor(A, 0, size, key);
}
```
• Finding number of occurrences of a Number in a sorted array:

```// Input: Indices Range [l ... r)
// Invariant: A[l] <= key and A[r] > key
int GetRightPosition(int A[], int l, int r, int key)
{
int m;

while( r - l > 1 )
{
m = l + (r - l)/2;

if( A[m] <= key )
l = m;
else
r = m;
}

return l;
}

// Input: Indices Range (l ... r]
// Invariant: A[r] >= key and A[l] > key
int GetLeftPosition(int A[], int l, int r, int key)
{
int m;

while( r - l > 1 )
{
m = l + (r - l)/2;

if( A[m] >= key )
r = m;
else
l = m;
}

return r;
}

int CountOccurances(int A[], int size, int key)
{
// Observe boundary conditions
int left = GetLeftPosition(A, -1, size-1, key);
int right = GetRightPosition(A, 0, size, key);

// What if the element doesn't exists in the array?
// The checks helps to trace that element exists
return (A[left] == key && key == A[right])?
(right - left + 1) : 0;
}```
• Apart from these functions there are also direct functions in stl which can be used. These are lower_bound and upper_bound.
lower_bound gives the iterator of the first appearance of key in array if key is in array, else it returns the iterator of the element just less than key. Similarly upper_bound returns the iterator of the next larger element than key in array in all cases. The example will make it clearer.

```#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort
#include <vector>       // std::vector

int main () {
int myints[] = {10,20,30,30,20,10,10,20};
std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20

std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

std::vector<int>::iterator low,up;
low=std::lower_bound (v.begin(), v.end(), 20); //          ^
up= std::upper_bound (v.begin(), v.end(), 20); //                   ^

std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
std::cout << "upper_bound at position " << (up - v.begin()) << '\n';

return 0;
}```