# Binary search (Java)

## [edit] Overview

An implementation of binary search in Java. This implementation is of illustrative purpose as Java provides static binary search methods in the Arrays and Collections classes. Searches for an element in a sorted list of elements. Returns the index of the element if found or the negative index where the element should be inserted to maintain ascending ordering. Therefore this is an implementation of binary search as an insertion search, not a pure exsistence search, which would only return if the element was found or not.

## [edit] Implementation

The method takes two arguments: The value to search and the list of values to search in. The input list must be sorted in ascending order prior to searching, else the result of this method is undefined. It must also contain at least one element. Through Java generics, the method can be used with any elements that extend Comparable, like Java number objects or strings, making Java 5 a requirement.

While we are searching, the interval [0, left] is empty or contains only list values < value. The interval [right, n-1] is empty or contains only list values > value. The remaining search interval is [left, right]. The parts left and right of that interval have been searched.

<<search>>=do{mid =(left + right)/ 2; midVal = values.get(mid);if(value.compareTo(values.get(mid))< 0)right = mid - 1;elseif(value.compareTo(values.get(mid))> 0)left = mid + 1;elsereturnmid;}while(left <= right);

Now left > right and the value was not found in the list. We now want to determine the index at which the element should be inserted to maintain the ordering. As the remaining searching interval is empty now, there is an interval *i* [0, n-1] with two disjunct intervals *i1* [0, left] and *i2* [right, n-1] with the following attributes: all indices in *i1* have list values < value, all indices in *i2* have list values > value and *i1* merged with *i2* equals *i*. We now have two possible cases:

Case a) *value < midVal & right = mid-1*. From the first part follows that *mid* is in interval [right, n-1] and from the second part follows that *mid* is at the left edge of the interval, so *mid* is the smallest index with list value > value. So in case a) an insertion must happen on index *mid*.

Case b) *value > midVal & left = mid+1*. From the first part follows that *mid* is in interval [0, left]. From the second part follows that *mid* is at the right edge of the interval. This means *mid* is the largest index with a list value < value, so in case b) we need to insert at *mid* + 1.

<<return>>=return(value.compareTo(midVal)< 0)? -mid : -(mid + 1);

## [edit] Usage

Illustration of the functionality using JUnit 4 unit tests for strings and integers:

<<test_strings>>=assertEquals(-1, BinarySearch.search("Billy", Arrays.asList("Anny","Emmy","Grammy")));

<<test_integers>>=assertEquals(-1, BinarySearch.search(2, Arrays.asList(1, 3, 4)));

The complete program:

<<BinarySearch.java>>=import static org.junit.Assert.assertEquals;import org.junit.Test;import java.util.Arrays;import java.util.List;publicclassBinarySearch{static<TextendsComparable<?superT>>intsearch(T value, List<T> values){intn = values.size();intmid, left, right; T midVal; left = 0; right = n - 1; search return}@TestpublicvoidtestStringSearch(){test_strings}@TestpublicvoidtestIntegerSearch(){test_integers}}

Download code |