Binary Search in Java

In this article, we are going to describe the implementation of a Binary Search in the Java language. So first you should understand what a Binary Search is. A Binary Search is applicable only to a sorted array and any data structure.

Generally, to find a value in an unsorted array, we should look through elements of an array one by one, until the searched value is found. In the case that a searched value is absent from the array, we go through all the elements. On average, the complexity of such an algorithm is proportional to the length of the array.

The situation changes significantly when an array is sorted. If we know it, the random access capability can be utilized very efficiently to find a searched value quickly. The cost of a searching algorithm reduces to the binary logarithm of the array length. For reference, log2(1 000 000) = 20. It means, that in the worst case, the algorithm requires 20 steps to find a value in a sorted array of a million elements or to say, that it doesn't access the entire array.

The following figure helps for a better understanding of the Binary Search concept:

The algorithm is quite simple. It can be done either recursively or iteratively. The algorithm consists of the following steps:

Step 1: Get the middle element;

Step 2: If the middle element equals the searched value, the algorithm stops; otherwise, two cases are possible:

1. Case 1: The searched value is less than the middle element. In this case, go to step 1 to search the half preceding the middle element.
2. Case 2: The searched value is greater than the middle element. In this case, go to step 1 to search the half following the middle element.

Step 3: Now we should define when iterations should stop. The first case is when the searched element is found. The second one is when subarray has no elements. In that case, we can conclude that the searched value is not present in the array.