Implementing Binary Search in Java

What is it?

Binary Search is a technique used to search sorted data sets. It works by comparing the middle element against the search value, if the search value is greater than the middle element a subset is created out of the upper half of the set. The same operation is then performed on the subset recursively until the value is either found and the index returned, or not found and -1 returned.

eg. If we start with with a set of ints: [1, 4, 6, 8, 9, 10, 11, 13, 15] and our search value = 11

  • Choose the middle element: 9
  • Is key == 9? No so we can’t break early
  • Is 9 > 11
  • No, so take the upper half and create a subset [10, 11, 13, 15]
  • Choose the middle element: 13 (4/2 =2 which is the third element in the array as arrays are zero based)
  • Is 13 > 11
  • Yes, so take the lower half and create a subset [10, 11]
  • Choose the middle element: 11
  • Is 11 == 11 yes – we have found our element

Binary Search in Java

I have created my own java binary search method:

    public static int binarySearch(int[] toSearch, int key) {
        int fromIndex = 0;
        int toIndex = toSearch.length - 1;

        while (fromIndex <= toIndex) {
            int midIndex = (toIndex - fromIndex) / 2 + fromIndex;
            int midValue = toSearch[midIndex];

            if (key > midValue) {
                fromIndex = midIndex + 1;
            } else if (key < midValue) {
                toIndex = midIndex - 1;
            } else {
                return midIndex;
            }
        }
        return -1;
    }

Take a look at Arrays.binarySearch() method to see the java source code implementation of the search. If you don’t have the java source code attached to your favourite IDE I suggest you do so, it’s a great way to learn how everything works.

Complexity

The complexity of the binary search is O(log n).

Why use Binary Search?

Binary Search is quicker than searching through every element (O(n)) as it halves the amount of elements to search each iteration. This halving means that after a strong growth curve at the beginning, it slowly flattens out as the size of the input data set increases, therefore it is good for large data sets.

More Info

There is a good introductory explanation of binary search and O notation here.

Advertisements

7 thoughts on “Implementing Binary Search in Java

  1. Pingback: An Intro to Big Oh Notation with Java « NerdGerl
  2. I think there is a problem when you calculate ‘midIndex’ :

    int midIndex = (toIndex – fromIndex / 2) + fromIndex;

    it doesn’t return the middle index at all. You will have to change the bracket but then I can’t understand what is the purpose of doing ‘+ fromIndex’

    anyway I know this is old post but maybe someone will look at this.

    Cheers

    • The fromIndex, in this context, is simply to give an offset. So it’s smallest number plus half the difference of the largest and smallest.

      I agree that the “/” precedence is broken here though.

      Any thoughts Nerdgerl???

  3. I think the code still have an issue.

    It goes into infinite loop when we have even number of items in the array and if we search the index of the last item (for ex: array length = 10)

    Let’s have [1, 4, 6, 8, 9, 10, 11, 13, 15, 17] and our search value = 17

    Details:

    Iteration | from | to | while(from<to) | mid | mid val
    0 0 9 true 4 9
    1 4* 9 true 6 11
    2 6* 9 true 7 13
    3 7* 9 true 8 15
    4 8* 9 true 8 15
    : : : : : :

    Couple of issues:
    1*) The idea here is to take the higher half by advancing the from index by adding 1 to the mid index
    Instead of: fromIndex = midIndex++;
    do: fromIndex = midIndex+1;

    2) while (fromIndex < toIndex) { should be changed to while (fromIndex <= toIndex) {

    I may be wrong here, but when I tested the code it worked only after making these changes.. 🙂

    Hope this helps..

  4. Just a minor error:

    Is 13 > 11
    No, …

    Actually 13 is greater than 11. So, it’s a yes, you take the lower half and create a subset [10, 11]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s