How to use and understand Binary Search on Java SE

By alex-arriaga
July 16, 2013
2 Comments

How to use and understand Binary Search on Java SE

Java is a Platform to create robust, secure and scalable stand-alone and enterprise web applications. It has a lot of classes and resources that make easy to develop many functionalities in systems. One of the most interesting parts of the Java API (Application Programming interface) is work with collections and generics. Basically, Java has three kinds of “collections”: Set, List and Map (this one is not necessarily a collection but it is enough alike than one, so its use doesn’t cause any problem, if we understand how collections work).

Well, in Java there is a special static class called Arrays (java.util.Arrays),

This class contains various methods for manipulating arrays (such as sorting and searching). This class also contains a static factory that allows arrays to be viewed as lists.

Today, I would like to show you how to use a method that implements Binary Search, but before we could check the official information about this method:

Binary Search method. Searches the specified array of ints for the specified value using the binary search algorithm. The array must be sorted (as by the sort(int[]) method) prior to making this call. If it is not sorted, the results are undefined. If the array contains multiple elements with the specified value, there is no guarantee which one will be found.

This method has a lot of overrides, for more information about them, please visit: http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#binarySearch(java.lang.Object[], java.lang.Object)

Now, imagine that we have the next code:

import java.util.*;

public class ArraysTest{
	public static void main(String [] args) {
		String [] colors = {"blue", "red", "green", "yellow", "orange"};

		// It is necessary to have an ordered array
		Arrays.sort(colors);
		for(String color : colors)
			System.out.print(color + " ");

		int index1 = Arrays.binarySearch(colors, "orange");
		int index2 = Arrays.binarySearch(colors, "violet");
		System.out.println("\norange => " + index1);
		System.out.println("violet => " + index2);
	}
}

The output is something like this:

blue green orange red yellow
orange => 2
violet => -5

According to the API:

Parameters:
- a – the array to be searched
- key – the value to be searched for
Returns:
- index of the search key, if it is contained in the array; otherwise, (-(insertion point) – 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
Throws:
- ClassCastException – if the search key is not comparable to the elements of the array.

Explanation

The first result after searching for “orange” is clear because “orange” was found in the index: 2.

Second result is a little more complex. Let me ask you, was “violet” found in the array? what should the index where “violet” be inserted? Well, see next image to understand better:

As you can see index:4 is where “violet” should be inserted. For this reason binarySearch return -5 (see next operation for more details):

-(insertion point) - 1 = -(4) -1 = -5

That’s it, at this moment.

Be happy with your code!

—

Alex Arriaga

Tags :
Source code

Alex Arriaga