Different versions of Binary Search:

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:
  // Returns location of key, or -1 if not found

  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;
}

Reference: http://www.geeksforgeeks.org/the-ubiquitous-binary-search-set-1/