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/

    Advertisements