Binary Search


Collapse Content

The last page covered some simple examples of recursion, which could have been coded with loops just as easily. In other cases, using recursion is considerably more 'natural' than using loops.

The Algorithm

You are given an array sorted in increasing order and would like to find the location of number n in it. While you could just search through the array in order, the goal is to find an optimal algorithm that will find the number much faster. Think about what algorithm you would use, and then click on the button below.

Binary Search Algorithm

The Code

Now that we've described an algorithm, let's convert it to code. We start with an empty method body (Hover over the parameter names for a description):

int binarySearch(int[] ar, int iMin, int iMax, int num){
    //algorithm here    
}

Next, let's fill in each step of the algorithm in code:

Step 1 - Check the middle Number. Let's declare a variable iMid to store the middle index1:

int binarySearch(int[] ar, int iMin, int iMax, int num){
    int iMid = (iMax+iMin) / 2;
    if(ar[iMid] == num){
        return iMid;
    }   
}

The binarySearch will now work when num happens to be right in the middle! When we're not that lucky, we'll need step 2:

Step 2. - Otherwise, check the 'correct' half next. If the number at the midpoint is greater than num, we'll want to check the left-hand side of the array. We can call binarySearch again with adjusted indices:

    //...previous code

    else if(ar[iMid]>num){
        return binarySearch(ar, iMin, iMid-1, num);
    }

This will call binarySearch with the same minimum index, but a new maximum index which is right before the number we just checked. If that condition isn't true, that means num is to the right:

    else{
        return binarySearch(ar, __, iMax, num);
    }

We now have a working binary search! To get to work we just pass in a sorted array, along with the minimum and maximum starting indices and the number we're looking for. For example:

int[] ar = {1,3,4,7,9,11,13};
int index = binarySearch(ar, 0, ar.length-1, 4);
System.out.println(index);

This code will print out 2, the index that 4 is located at.

Here's a diagram of a binary search in action:

binary Search diagram

What happens:

  1. The initial call starts searching from cell 0 to the last cell in the array
  2. binarySearch sees that 7 (located at index 3) is bigger than 4, so it calls binarySearch on 0 to 2.
  3. 3 is less than 4, so binary search moves up and finally finds 4.

Finishing the Search

The search works, but there's one issue - what if the number isn't found in the array? There's nothing to stop the indices from 'passing' each other and the search will continue until there's a StackOverflow error.

So we need to add another base case that checks for this condition:

if(iMax < iMin){
  return -1;
}

this will return -1 when the iMax passed iMin, which means the number isn't in the array (assuming it's sorted).

It's important to cover all "exit possibilities" so that the recursive function doesn't try going on forever.

The complete binarySearch is below. To see it visualized, click here.

int binarySearch(int[] ar, int iMin, int iMax, int num){
    if(iMax < iMin){
        return -1;
    }
    int iMid = (iMax+iMin)/2;
    if(ar[iMid] == num){
        return iMid;
    }
    else if(ar[iMid]>num){
        return binarySearch(ar, iMin, iMid-1, num);
    }       
    else{
        return binarySearch(ar, iMid+1, iMax, num);
    }       
}

1. This is the simplest way to find the middle number, though it won't work for very large integers in Java.

Challenge

What value should be put in the blank above so the correct minimum index is passed to binarySearch?

Please sign in or sign up to submit answers.

Alternatively, you can try out Learneroo before signing up.

Challenge

The method doStuff takes in one square number. Create a separate recursive method that returns the square root of a given number. Call that method from doStuff and return the answer to be printed out.

Do not use any built in methods for calculating the square-root and don't try searching through all the numbers. Instead, use a binary-style search to home in on the actual square root.

(To make it simpler, the input will just contain square numbers.)

Please sign in or sign up to submit answers.

Alternatively, you can try out Learneroo before signing up.

Comments

  • Why r.binarySearch?

  • Dear admin,

    When clicking on the Raw I/O option under Input I see "8":

    Input

    8 <<<<No Square
    25
    81
    225
    841
    1024
    7056
    36
    144

    Correct Output
    5
    9
    15
    29
    32
    84
    6
    12

    cont...
  • @David, the first number in raw input states how many cases there will be, it's not one of the actual cases.

  • Awesome site this is!

  • how do i know what is desired number? Should I make anarray from 0 to a, than start at midle checking if that number to power 2is a?

  • @armands, you don't actually need an array, but that's the right idea (see the hint).

  • Hi guys, i have written this code https://ideone.com/eFWUiZ its kind of bad, i know it , i suck at recursion but it was a bit logical for me i really don't know where i'm missing up

  • See if you can keep it organized. If you don't have the right number, see if it's larger or smaller and call your recursive method accordingly. You don't want to have two methods calling each other since that's just confusing. Look over the provided code for binary search and see how to adjust it for the "square root search" problem.

    cont...
Contact Us