Java binary search function

Java Guides

In computer science, searching is the process of finding an item with specified properties from a collection of items. The items may be stored as records in a database, simple data elements in arrays, text in files, nodes in trees, vertices and edges in graphs, or they may be elements of other search spaces.

Why do we need Searching?

Searching is one of the core computer science algorithms. We know that today’s computers store a lot of information. To retrieve this information proficiently we need very efficient search algorithms.

There are certain ways of organizing the data that improve the searching process. That means, if we keep the data in proper order, it is easy to search for the required element. Sorting is one of the techniques for making the elements ordered. In this article, we will see different search algorithms.

Binary Search with Example

Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, the data collection should be in the sorted form.

Let us consider the problem of searching for a word in a dictionary. Typically, we directly go to some approximate page [say, middle page] and start searching from that point. If the name that we are searching for is the same then the search is complete. If the page is before the selected pages then apply the same process for the first half; otherwise, apply the same process to the second half. Binary search also works in the same way. The algorithm applying such a strategy is referred to as a binary search algorithm.

How Binary Search Works?

For a binary search to work, it is mandatory for the target array to be sorted. We shall learn the process of binary search with a pictorial example.

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

Now we compare the value stored at location 4, with the value being searched, i.e. 10. We find that the value at location 4 is 8, which is not a match. As the value is greater than 8 and we have a sorted array, so we also know that the target value must be in the upper portion of the array.

low = mid + 1 mid = low + (high - low) / 2 

The value stored at location 7 is not a match, rather it is more than what we are looking for. So, the value must be in the lower part from this location.

Binary Search Implementation using Java

Let’s write a source code for binary search in Java. There are many ways we can write logic for binary search:

1. Iterative implementation
2. Recursive Implementation
3. Using Arrays.binarySearch()
4. Using Collections.binarySearch()

Iterative Implementation

public class BinarySearch < public int binarySearchIteratively(int[] sortedArray, int key) < int low = 0; int high = sortedArray.length - 1; int index = Integer.MAX_VALUE; while (low  high) < int mid = (low + high) / 2; if (sortedArray[mid]  key) < low = mid + 1; > else if (sortedArray[mid] > key) < high = mid - 1; > else if (sortedArray[mid] == key) < index = mid; break; > > return index; > public static void main(String[] args) < int[] sortedArray = < 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 >; int key = 6; BinarySearch binSearch = new BinarySearch(); int index = binSearch.binarySearchIteratively(sortedArray, key); System.out.println("Search element found " + key+ " in location index : " + index); > >

Search element 6 found in location index : 7 

The binarySearchIteratively method takes a sortedArray, key & the low & high indexes of the sortedArray as arguments. When the method runs for the first time the low, the first index of the sortedArray, is 0, while the high, the last index of the sortedArray, is equal to its length – 1.

The middle is the middle index of the sortedArray. Now the algorithm runs a while loop comparing the key with the array value of the middle index of the sortedArray.

Recursive Implementation

public class BinarySearch < public int binarySearchRecursively(int[] sortedArray, int key, int low, int high) < int middle = (low + high) / 2; if (high  low) < return -1; > if (key == sortedArray[middle]) < return middle; > else if (key  sortedArray[middle]) < return binarySearchRecursively(sortedArray, key, low, middle - 1); > else < return binarySearchRecursively(sortedArray, key, middle + 1, high); > > public static void main(String[] args) < int[] sortedArray = < 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 >; int key = 6; BinarySearch binSearch = new BinarySearch(); int index = binSearch.binarySearchRecursively(sortedArray, key, 0, sortedArray.length -1); System.out.println("Search element found in location index : " + index); > >

Search element found in location index : 7 

The binarySearchRecursively method accepts a sortedArray, key, the low and high indexes of the sortedArray.

Using Arrays.binarySearch()

public class BinarySearch < public int runBinarySearchUsingJavaArrays(int[] sortedArray, Integer key) < int index = Arrays.binarySearch(sortedArray, key); return index; > public static void main(String[] args) < int[] sortedArray = < 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 >; int key = 6; BinarySearch binSearch = new BinarySearch(); int index1 = binSearch.runBinarySearchUsingJavaArrays(sortedArray, key); System.out.println("Search element found in location index : " + index1); > >

Search element found in location index : 7

Using Collections.binarySearch()

public class BinarySearch < public int runBinarySearchUsingJavaCollections(ListInteger> sortedList, Integer key) < int index = Collections.binarySearch(sortedList, key); return index; > public static void main(String[] args) < Integer[] sortedArray = < 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 >; int key = 6; BinarySearch binarySearch = new BinarySearch(); int index1 = binarySearch.runBinarySearchUsingJavaCollections(Arrays.asList(sortedArray), key); System.out.println("Search element found in location index : " + index1); > >

Search element found in location index : 7 

Auxiliary Space: O(1) in the case of iterative implementation. In the case of recursive implementation, O(Logn) recursion call stack space.

Источник

Java binary search function

We can verify the theoretically derived time complexity with the program BinarySearchRuntime from the GitHub repository. The program generates random arrays with 10,000 to 200,000,000 elements and searches them for a randomly selected element.

Since the times are in the nanosecond range, each measurement consists of searches for 100 different keys. The measurement is repeated 100 times for each array size; then, the median is printed. The following graph shows the average runtime in relation to the array size:

The logarithmic progression can be seen very well.

Binary Search vs. Linear Search

With linear search, the best case is finding the element we are looking for in the first step. In the worst case, we have to search the entire array. In the average case, half of the entries. With n entries, that is n/2 search steps. The duration of the search increases linearly with the number of entries. We say:

The time complexity of the linear search is O(n).

We can measure the runtime of linear search with the LinearSearchRuntime program. The following image shows the comparison of the runtimes of binary and linear search. I had to reduce the range to 100,000 elements to be able to recognize at least a minimal increase of the measured values for the binary search:

We can see the linear time of the linear search very nicely. It is also apparent that the binary search is orders of magnitude faster than the linear search.

Runtime of Binary Search for Small Arrays

Due to the higher complexity of the binary search code, linear search can be faster for small arrays. The following diagram shows a section of the comparison of run times for up to 500 elements. Each measurement point is the median of 100 measurements with 10,000 repetitions each.

That confirms the assumption. For arrays up to a maximum of about 230 elements, linear search is faster than binary search. Of course, this is not a general statement but applies only to my laptop and the JDK I currently use.

You can once again nicely see the linear time – O(n) – compared to the logarithmic time – O(log n).

Runtime of Binary Search in a LinkedList

In the chapter Binary Search in the JDK, I mentioned that the Collections.binarySearch() method can also be applied to a LinkedList . Collections.binarySearch() distinguishes internally between lists that implement the RandomAccess interface, such as ArrayList , and other lists. For lists with «random access», a regular binary search is performed.

To access the middle element in lists without random access, we would have to follow the elements from the beginning to the middle, element by element. From there, we would again reach the center of the left or right half by following the list, element by element. The following diagram should illustrate this:

For example, to find the position of 19, we would first have to follow the orange arrows to the center, then the blue arrows back to 23, and finally the yellow arrow to 19.

That works only with a doubly linked list. For iterating left in a singly linked list, you would have to jump back to the beginning and, from there, follow the arrows to the right again.

No matter if singly or doubly linked – in any case, we have to iterate over more elements than with linear search. While we have an average of n/2 search steps in the linear search in total, we already iterate over n/2 elements to reach the middle in the first step of the binary search. In the second step, we iterate over n/4 elements; in the third step, we iterate over n/8 elements, and so on.

So at first glance, binary search makes absolutely no sense in a LinkedList .

When Is Binary Search in a LinkedList Useful?

Nevertheless, binary search in a LinkedList can be faster than linear search. Although we have to iterate over more elements (as shown in the previous section) – the number of comparisons remains in the order of O(log n)!

Depending on the cost of the comparison function – which can be significantly higher for an object than for a primitive data type – this can make a considerable difference. So if you ever need to search in a LinkedList , it’s worth trying binary search with Collections.binarySearch() and comparing it to linear search.

Summary

This article has shown the principle of binary search and its advantages over linear search for sorted arrays and lists. I demonstrated the theoretically derived time complexity on an example. I also showed that binary search could be useful for a doubly linked list.

A very similar technique is the search in a binary search tree.

If you liked the article, feel free to leave me a comment or share it using one of the share buttons at the end. If you want to be informed when the next articles are published, sign up for my newsletter using the form below.

Источник