Binary Search is the fastest algorithm for finding an element in a sorted list. Also it’s easy to implement what we’re going to show in this post.

The procedure is simple:

1. Take element from the center and compare with expected value.
2. If found return its index.
3. If expected value is bigger, repeat from step 1, but only for part of array from the second half. Because the array is sorted we know that everything from the first half is smaller than the target element, so no need to compare.
4. If expected value is lower, repeat from step 1, but only for part of array from the first half.
5. Return some value that indicates that the expected value was not found (usually -1) or negative index – 1 of place where it can be inserted, to simplify insertion for users (optional, but easy to do).

• input array must be sorted
• computational complexity in the worst case is O(log n + 1) (not found), best is O(1) (hit on the first guess)
• returns index of target element when found
• returns negative index minus one of insertion point of target element, in case when was not found

In this implementation we are working with integers, but it can be easily changes to work with any Java objects that are comparable (or by providing custom Comparator):

package com.farenda.tutorials.algorithms.searching;

public class BinarySearch {

    public static int find(int[] numbers, int target) {
        int min = 0, max = numbers.length-1;

        while (min <= max) {
            int pos = (min+max) / 2;
            if (numbers[pos] == target) {
                return pos;
            }
            if (numbers[pos] < target) {
                min = pos + 1;
            } else {
                max = pos - 1;
            }
        }

        // +1, because 0 belongs to positive indices
        return -(min+1);
    }
}

Let’s write some JUnit tests to verify our implementation. We can use Fibonacci numbers as our sorted array of numbers:

package com.farenda.tutorials.algorithms.searching;

import java.util.Arrays;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class BinarySearchTest {

    private static final int[] FIBOS
            = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 };

    // Tests will go here:
}

@Test
public void shouldFindIndexOfNumber() {
    // Our version:
    assertEquals(3, BinarySearch.find(FIBOS, 3));
    assertEquals(9, BinarySearch.find(FIBOS, 55));

    // JDK version:
    assertEquals(3, Arrays.binarySearch(FIBOS, 3));
    assertEquals(9, Arrays.binarySearch(FIBOS, 55));
}

Here we’ve added calls for Binary Search method from java.util.Arrays just to compare the results.

In the case when expected number is not found it’s easy to a return pointer to a place where it can be inserted. Here we’re going to verify that it works:

@Test
public void shouldReturnNegativeInsertionPointWhenNotFound() {
    // Our version:
    assertEquals(-1, BinarySearch.find(FIBOS, 0));
    assertEquals(-5, BinarySearch.find(FIBOS, 4));

    // JDK version:
    assertEquals(-1, Arrays.binarySearch(FIBOS, 0));
    assertEquals(-5, Arrays.binarySearch(FIBOS, 4));
}

• JUnit Tutorial
• Java BinarySearch with custom Comparator