Binary Search using recursion

Binary search is a method to search through a sorted container in order to find a particular value.

Remember that “Guess the number” game? Let’s look at the following scenario by applying the Binary Search Algorithm in order for you to understand how Binary Search works.

The Guessing Game

Pick a number from 0 – 100 and depending on your guess, I’ll either say Correct, Higher, or Lower. What would you choose?

0

1

…

49

50

51

…

99

100

Well, 50 of course! Why? Best case you get it correct. Worst case you’ll either get a “Higher” or “Lower”. Now think about the following, if you got “Higher” you eliminated 0-49, or 51-100 if “Lower”, in other words, you eliminate HALF the possibilities.

50

51

…

74

75

76

…

99

100

Well, let’s say it was “Higher”. What would you guess after? 75. Since it’s in between 50 – 100. If you didn’t guess correctly, you’ll be facing the similar scenario as before. You’ll end up eliminating half the possibilities!

Getting started on the Binary Search Algorithm

Let’s break up the rules for the Binary Search Algorithm.

• If the number guessed is correct, return the location of the element
• If the number is at a “Higher” location, eliminate the lower half, else eliminate the upper half

Given this information, what would we need for our function header?

Header for Binary Search

We’d need the container and values indicating where our lower and higher boundary are. We’ll be returning the location of the value, else -1 if not found. We’ll also need the key we are looking for.

int binarySearch(vector  vec, int low, int high, int key) {

Next, what would our base cases be? When the element we “pick” is correct, or we exhausted searching through our container.

Base Case for Binary Search

Like mentioned before, the first element to be compared to in our container would be the middle element. We’d also check to see if we exhausted our search by the following base case.

int binarySearch(vector  vec, int low, int high, int key) {

    // We exhausted our search
    if ( low > high ) {
         return -1;
    } 

    // The middle element
    int mid = (low + high)/2;

    if ( vec[mid] == key ) {
        return mid;
    }

If you don’t understand why we have our initial base case, follow along. You’ll understand shortly.

Next, how would we break down our Binary Search on the next recursive call? Well, by simply assigning a new low, or high depending if they key was higher or lower than the one compared to.

Binary Search using Recursion

int binarySearch(vector  vec, int low, int high, int key) {

    // We exhausted our search
    if ( low > high ) {
         return -1;
    } 

    // The middle element
    int mid = (low + high)/2;

    if ( vec[mid] == key ) {
        return mid;
    }

    //If middle index value is larger than our key,
    //we search the lower half of the vector
    //else we search the upper half

    else if ( vec[mid] > key ) {
         return binarySearch(vec, low, mid-1, key);
    } else {
         return binarySearch(vec, mid+1, high, key);
    }
}

If you didn’t understand our initial base case, run through this algorithm using our recursive calls on a small vector without the key you are looking for and you’ll realize why our base case works as follows.

Going further

1. Can you make a helper function to make this calling this function cleaner for the user?
2. Would this algorithm work using an unsorted array?