Implementing binary search of an array in Java and Python

A binary search divides a range of ordered values into halves (two equal portions) and continues to split the array until the position of unknown value is found. It is an example of a "divide and conquer" algorithm. One of the common ways to use binary search is to find an unknown item in an array. It has the run-time complexity of O(log n).

An array is a container object that holds a fixed number of values of a single type. In Java programming language the length of an array is established when the array is created. But in Javascript, neither the length of a JavaScript array nor the types of its elements are fixed. Python programming language considers arrays as lists that can contain mixed data types.

Following paragraphs try to describe the binary search in details.

Binary search works with only sorted collections. That is due to the binary search looks for a particular item by comparing the middle element of the array. If it matches the item we look for, the index of the item is returned. If the item we are looking for is greater than the middle item, then the item is searched in the sub-array (array is divided into two sub-arrays) to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-arrays until the size of the sub-array reduces to zero.

The following is our sorted array and let us assume that we need to search the location of value 11 using binary search.

First, we need to find the middle item of the array using following formula.

middle index = lowest index + (highest index - lowest index) / 2

By using the above formula we get the 0 + (9 - 0 ) / 2 = 4.5 (round it) as middle index. So the fourth item is the middle item.

The value stored in the fourth position is less than the value we are looking for, so the value must be in the upper position of the array.

Again we use the above formula to find the middle index. Now lowest index value is equal to the previous value of middle index + 1. Because we are in the upper position of the array.

lowest index = middle index (4) + 1

middle index = lowest index + (highest index - lowest index) / 2

Now the middle index is 7. But the value we are searching for is number 11.

Now we need to change the direction of the search.

Now we have a sub-array with 11 and 15. But the highest index is lowest index - 1 and the lowest index is same as the previous time.

highest index = middle index (7) - 1

middle index = lowest index + (highest index - lowest index) / 2

Now it will check the first element and get the value to compare. Value is 11 and we are looking for 11. 

Pseudocode for binary search

Pseudocode is an artificial and informal language that helps programmers develop and understand algorithms. Due to the differences between programming languages, it is a wise step to write the algorithm using pseudocode. 

An algorithm is merely the sequence of steps taken to solve a problem. To implement any algorithm, you must be able to understand every detail of the problem.

I have tried to write the pseudocode in plain English for the beginners.

1. Define lowest_index as 0 and the highest index as length of the array.
2. Compute middle array.
3. Compare the middle array with the value we need to search.
4. If the middle array value (not index) equal to the value we are searching for return it.
5. If the value we searching for is too large, that is, middle item > value we search then the highest index - 1.
6. Otherwise, the guess is too small set the middle_index + 1.
7. Go back to step two.

Python code for binary search

Here is the python code sample for the binary search. It is the recursive implementation of the binary search. You can copy the code using the following gist.

	def search(arr, x, lowest_index, highest_index):
	#find the middle index
	middle_index = lowest_index + (highest_index - lowest_index) / 2
	print "Middle index is ", middle_index
	# checks whether the value is in the middle index
	if (arr[middle_index] == x):
	return middle_index
	elif (arr[middle_index] > x):
	# checks in <- direction
	return search(arr, x, lowest_index, highest_index - 1)
	else:
	# checks in -> direction
	return search(arr, x, middle_index + 1, highest_index)
	# array to pass as variable
	arr = [1, 3, 5, 7, 9, 11, 15, 17, 19]
	# result of the search
	index = search(arr, 3, 0, len(arr))
	#checks whether result is -1 or other integer value
	if index != -1:
	print "Element is present at", index
	else:
	print "Your searched item is not in the array"

view raw binary_search.py hosted with ❤ by GitHub

Java code for binary search

Here is the Java code sample for the binary search. You can copy the code using the following gist.

	package uk.co.stableweb;
	public class BinarySearch {
	public static void main(String[] args) {
	// Create an array
	int[] array = {1, 3, 5, 7, 9, 11, 15, 17, 19};
	// Initially lowest index is 0
	int lowestIndex = 0;
	// Initially highest value is the length of array
	int highestIndex = array.length;
	// Value to be searched.
	int searchValue = 3;
	// Run the while loop until highest value is bigger than lowest value
	while(highestIndex >= lowestIndex){
	// Compute the middle index
	int middleIndex = (lowestIndex + highestIndex) / 2;
	// If the middle item matches to the search value print it and break the loop.
	if(array[middleIndex] == searchValue){
	System.out.println("Element is at " + middleIndex);
	break;
	}
	// If the search value is larger than the middle value add 1 to the middle value and
	// assign to lowest value
	if(array[middleIndex] < searchValue){
	lowestIndex = middleIndex + 1;
	}
	// If the search value is smaller than the middle value reduce 1 from middle value and
	// assign it to highest value
	if(array[middleIndex] > searchValue){
	highestIndex = middleIndex - 1;
	}
	}
	}
	}

view raw BinarySearch.java hosted with ❤ by GitHub

There are lots of resources to understand binary search. The following video by CS50 explains the algorithm visually. If you are a visual learner, you can watch the following video to understand the algorithm.