Programming Tutorials and Interview Questions

*Binary search* operates on a sorted list and finds the given element by comparing it with the middle element of the list. The comparison determines whether the middle element is equal to the given element, less than the input or greater. *Binary search* delivers better performance than sequential search by sorting the elements of the list ahead of searching.

*Binary search* looks at the middle element of the list and see if the element *sought-for* is found. If not, than it compares the *sought-for* element with the middle element of the list and check whether the middle element is larger than the element we are trying to find. If so, we keep looking in the first half of the list; otherwise, we look in the second half. It cuts the number of elements to be compared by half. We keep going in the same way until the item is found or it is determined that the *sought-for* element is not present in the list.

The input to *binary search* is an indexed collection `A`

of elements. Each element `A[i]`

has a key value *k _{i}* that can be used to identify the element. These keys are totally ordered, which means that given two keys,

Given an ordered collection of elements as an array, the following program develops a class `BinarySearch`

that contains a parameterized `static`

method `binarySearch`

for any base type `T`

. Note that Java provides the `java.util.Comparable`

interface that contains a single method, `compareTo`

. Any class that correctly implements this interface guarantees a total ordering of its instances.

import java.util.*; class BinarySearch { /* Apply binary search to search the sorted list (of type T) for the given item. */ public static <T extends Comparable<T>> boolean binarySearch (T[] list, T searchKey) { // null is never included in the list if (searchKey == null) { return false; } int low = 0, high = list.length - 1; while (low <= high) { int mid = (low + high)/2; int rc = searchKey.compareTo(list[mid]); if (rc < 0) { // searchKey is less than list[i] high = mid - 1; } else if (rc > 0) { // searchKey is greater than list[i] low = mid + 1; } else { // found the item. return true; } } return false; } } public class BinarySearchDemo { public static void main (String[] args) { Integer arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; Integer searchKey = new Integer("7"); /* Uses binary search and search through the sorted list */ System.out.println("Search key " + searchKey + " is found? " + BinarySearch.binarySearch (arr, searchKey)); } } OUTPUT ====== Search key 7 is found? true

Above *binary search* implementation in Java uses three important variables: `low`

, `high`

, and `mid`

. `low`

is the lowest index of the current sub-array being searched, `high`

is the upper index of the same sub-array, and `mid`

is the midpoint of the sub-array.

*Binary search* adds a small amount of complexity for large performance gains. The complexity can increase when the collection is not stored in a simple in-memory data structure, such as an array. There must be a way to access element `A[i]`

for `0 <= i < n`

in the collection based upon the natural order of the elements in the collection, as represented by the `Comparable`

interface. A large collection might need to be kept in secondary storage, such as a file on a disk. In such a case, the i^{th} element is accessed by its offset location within the file. Using secondary storage, the time required to search for an element is dominated by the costs to accessing the storage; other solutions related to *binary search* may be appropriate.

*Binary search* divides the problem size approximately in half every time it executes the loop. The maximum number of times the collection of size *n* is cut in half is *log(n)*, if *n* is a power of 2; otherwise, it is ⌊*log(n)*⌋. If we use a single operation to determine whether two items are equal, lesser than, or greater than (as is made possible by the Comparable interface), then only ⌊*log(n)*⌋ comparisons are needed, resulting in a classification of *O(log n)*.

In this tutorial we discussed *binary search* algorithm and implemented it through a Java program. Hope you have enjoyed reading this tutorial. Please do write us if you have any suggestion/comment or come across any error on this page. Thanks for reading!

The BBCâ€™s technology correspondent Rory Cellan-Jones gets a beer poured for him by a robotic barman - but how long does it take?

US politicians have voted to let ISPs gather and sell data about what Americans do online.

Customers who suffer poor service could get automatic payouts under Ofcom's plan.