Binary Search

Binary search is the most prominent example of a Divide and Conquer algorithm.
Suppose you are given an array of size in sorted order and you have to return the index of an element.

Basic algorithm is

initialize low = 0, high = N, mid = (low + high)/2
check if element is at position mid; if found, return  
else depending upon value of mid is lower or greater, we explore the right side of the array or the left side

Sample recursive function code in C++:

int binary_search(int A[], int key, int imin, int imax)
{
  // test if array is empty
  if (imax < imin)
    // set is empty, so return value showing not found
    return KEY_NOT_FOUND;
  else
    {
      // calculate midpoint to cut set in half
      int imid = midpoint(imin, imax);

      // three-way comparison
      if (A[imid] > key)
        // key is in lower subset
        return binary_search(A, key, imin, imid - 1);
      else if (A[imid] < key)
        // key is in upper subset
        return binary_search(A, key, imid + 1, imax);
      else
        // key has been found
        return imid;
    }
}

Sample iterative solution in C++:

int binary_search(int A[],int N,int key){

    // considering 1 based index
    int low , high , mid ;
    low = 1 ;
    high = N ;
    while(low <= high){
        mid = (low + high)/2 ;
        if(A[mid] == key){
            return mid ; // a match is found
        }else if(A[mid] < key){ // if middle element is less than the key 
            low = mid + 1 ;     // key will be right part if it exists
        }else{
            high = mid - 1 ;    // otherwise key will be in left part if it exists
        }
    }
    return -1 ; // indicating no such key exists 
}

Common Variations of BinarySearch:

  1. LowerBound: find an element in a sorted array of intergers such that , where key is given.
  2. UpperBound: find an element in a sorted array of intergers such that , where key is given.

UpperBound Implementation in C++:

int UpperBound(int A[],int N,int K){
    int low , high , mid ;
    low = 1 ;
    high = N ;
    while(low <= high){
        mid = ( low + high ) / 2 ; // finding middle element 
        if(A[mid] > K && ( mid == 1 || A[mid-1] <= K )) // checking conditions for upperbound
            return mid ;
        else if(A[mid] > K) // answer should be in left part 
            high = mid - 1 ;
        else                // answer should in right part if it exists
            low = mid + 1 ;
    }
    return mid ; // this will execute when there is no element in the given array which > K
}

LowerBound Implementation in C++:

int LowerBound(int A[],int N,int K){
    int low , high , mid ;
    low = 1 ;
    high = N ;
    while(low <= high){
        mid = ( low + high ) / 2 ; // finding middle element 
        if(A[mid] >= K && ( mid == 1 || A[mid-1] < K )) // checking conditions for lowerbound
            return mid ;
        else if(A[mid] >= K) // answer should be in left part 
            high = mid - 1 ;
        else                // answer should in right part if it exists
            low = mid + 1 ;
    }
    return mid ; // this will execute when there is no element in the given array which >= K
}

NOTE : C++ STL (Standard Template Library) already contains implementation of all of these functions. Check out here for additional knowledge binarysearch, lowerbound, upperbound

 
Related challenge for Binary Search
Go to Top
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score