Binary search (Java)

From LiteratePrograms
Jump to: navigation, search
Other implementations: C | C++ | 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;
    else if (value.compareTo(values.get(mid)) > 0)
        left = mid + 1;
    else
        return mid;
} 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;

public class BinarySearch {
	static <T extends Comparable<? super T>> int search(T value, List<T> values) {
		int n = values.size();
		int mid, left, right;
		T midVal;
		left = 0;
		right = n - 1;
		search
		return
	}
	@Test
	public void testStringSearch() {
		test_strings
	}
	
	@Test
	public void testIntegerSearch() {
		test_integers
	}
}
Download code
hijacker
hijacker
hijacker
hijacker