Search Algorithms

Comparision of the efficiancy of Binary Search (top), versus the efficiancy of sequential
search (bottom). The cell that is being checked for the value is being marked with 'X'.

For the purposes of ICS AP two searching algorithms need to be learned. Sequential search, and Binary Search. Both these algorithms are used to find the index of a specified value in an array. They find the needle in the haystack, if you will.

Each of those two sorting algorithms have their own drawbacks, and should be used in specific situations. There is no truly optimal search algorithm for every situation. Both of these searching algorithms have their advantages and their drawbacks.

For the purposes of this tutorial, if a loop fails to find the element in the array, the value returned will be -1. This value is chosen as -1 can never be an index in Java, yet it can still be stored within the int data type.

Sequential Search

Sequential search is perhaps one of the most simple and straight forwards searching algorithms. The general premise for this algorithm is very simple, you just go check each index of the (in this case) Array until you find the result. If you find the result, then you just return the index value where that item lies. If the loop terminates you return a value that cannot be an index.

Sequential search is generally considered a pretty slow searching algorithm as it has to run through each element in the array individually. Sequential search is generally considered a O(N) algorithm where N is the length of the array since that’s its worst case performance.

The one upside sequential search has is that it works on an unsorted array. Other searching algorithms do not work on an unsorted array.

The most common implementation of sequential search usually looks something like this:

public static int sequentialSearchIntArray(int needle, int[] haystack) {
	for (int i = 0; i < haystack.length; i++)
		if (haystack[i] == needle)
			return i;
	
	return -1;
}
		

Binary Search

Binary search is a very efficient algorithm, however it has a large Achilles heel. It’s limitations mean that it cannot often be used, but when it can it outperforms sequential search in nearly every case, the image above demonstrates this. The most simple way to explain binary search is that the center of the array is checked, if that value is greater than the target value, then the center between the beginning and the center of the array is checked, otherwise it checks the other way, continually dividing the array into halves. If the checked value is found, return that index, if the lower bound goes above the higher bound, then return a value that cannot be an index.

In the above image binary search only takes 4 iterations, while sequential search takes 8. This is because binary search runs in O(log(N)) time. Because of this it can search huge arrays in a very small amount of time.

The one major issue that binary search has is that it only works on a sorted array. This is because the direction that the algorithm chooses to search next is based upon the checked value’s relationship to the target value.

A general non-recursive implementation of binary search generally looks as follows:

public static int binarySearchIntArray(int needle, int[] haystack) {
	int low = 0, high = haystack.length - 1;
	
	while (low <= high) {
		int midpoint = (low + high) / 2;
		
		if (haystack[midpoint] == needle)
			return midpoint;
		
		if (haystack[midpoint] < needle)
			low = midpoint + 1;
		else
			high = midpoint - 1;
	}
	
	return -1;
}