In this tutorial on binary search algorithm implementation in java, we will start by looking at how the binary search algorithm works, understand the various steps of the algorithm, and its two variants – iterative and recursive binary search implementations. Next, we will see the java implementation of iterative binary search, followed by its explanation. Lastly, we will see the implementation of recursive binary search in java and its explanation.

What is Binary Search

Binary Search algorithm searches for an element in an ordered list (or, dictionary) using a process in which at every step of the algorithm the list remaining to be searched gets divided by half.

Lets say we have an element `'e'`

which we have to search in an ordered list `'L'`

. At the beginning of binary search, 2 pointers named `low`

and `high`

are initialized to the first and the last elements of `'L'`

.

From here on the binary search algorithm proceeds in the following 3 steps which together constitute one iteration of the binary search algorithm.

**STEP 1:**Pointer named`'mid'`

is calculated as`'(low+high)/2'`

. This pointer`'mid'`

points to the middle element of the ordered list portion which will be searched in this iteration.**If the element at**, then the element to be searched is declared found and the iteration along with the algorithm ends.`'mid'`

position is equals`'e'`

**STEP 2:**If element at`'mid'`

is found not equal to`'e'`

in*STEP 1*, then it is checked**whether**. If yes, then`'e'`

is less than element at`'mid'`

`'high'`

is set to the position`'mid-1'`

while`'low'`

remains as it is. The iteration ends and control moves back to*STEP 1*.**STEP 3:**. Pointer`'e'`

is now determined to be greater than element at`'mid'`

`'low'`

is set to the position`'mid+1'`

while`'high'`

remains as it is. The iteration ends and control moves back to*STEP 1*.

As you can see above, the list to be searched gets progressively divided by half in every iteration iff the element to be searched is not found. The ordered nature of the list allows us to take this decision. If `'e < element at mid'`

, then it makes no point to search among elements at `'mid'`

or higher positions; so we reset the `'high'`

pointer to `'mid-1'`

. Similarly, if `'e > element at mid'`

, then we can be sure that `'e'`

will not be found at `'mid'`

or lower position; allowing us to reset `'low'`

to `'mid+1'`

position.

In this way we progressively keep on dividing the remaining list to be searched by half with every iteration by losing mid and lower half, or mid and higher staff every time. This nature of binary search algorithm makes it much more efficient than linear search(brute force approach) which has time complexity of **O(n)**. **Binary search, by virtue of its progressively dividing method, has much lower time complexity of O(log n)**.

The repititive nature of the algorithm is implemented via iterations. It can also be implemented via recursion as at the end of every iteration of the algorithm, it calls the same 3 steps, or itself again recursively.

You can see a whiteboard animation based video explanation of how binary search works and get a code walk-through of the recursive and iterative variants of the algorithm in Java in this YouTube video

Let us now see how to implement the binary search algorithm in Java. We will first see the iterative implementation of binary search, followed by the recursive implementation.

Iterative Binary Search Implemention in Java

package com.javabrahman.algorithms; import java.util.Arrays; import java.util.List; import java.util.Scanner; public class BinarySearch { public static void main(String args[]) { //List of Integers List<Integer> integerList = Arrays.asList(1, 10, 55, 66, 68, 85, 101, 110, 125, 179, 201, 356, 1000); //Scan number to be searched and convert to Integer Scanner scanner = new Scanner(System.in); String str = scanner.nextLine(); Integer noToSearch = Integer.parseInt(str); //Sort the List to make sure it is ordered integerList.sort(Integer::compareTo); //Set low & high for complete list int low = 0, high = integerList.size() - 1; //Perform Binary Search Iterative boolean found= performBinarySearchIterative(integerList,noToSearch,low,high); if (!found) { System.out.println(noToSearch + " not found"); } } public static boolean performBinarySearchIterative(List<Integer> integerList, Integer noToSearch, int low, int high) { while (low <= high) { int mid = (low + high) / 2; if (integerList.get(mid).equals(noToSearch)) { System.out.println(noToSearch +" found at index "+ mid); return true; } else if (noToSearch < integerList.get(mid)) { high = mid - 1; } else { low = mid + 1; } } return false; } }

**Inputs - 68 & 101, and corresponding output of the above code**

68 found at index 4

1001

1001 not found

- The
`main()`

method of`BinarySearch`

class starts off with defining a list of integers of size`13`

, named`integerList`

. - Next the number to be searched is taken as input from the user using a
`Scanner`

instance, and stored in`noToSearch`

variable. - The key pointers to
`low`

and`high`

are assigned values of`0`

and`12`

respectively(`integerList.size() - 1`

has value`12`

). - Next,
`performBinarySearchIterative()`

method is invoked with`integerList`

,`noToSearch`

,`low`

and`high`

. `performBinarySearchIterative()`

does the following -- Contents of the method are inside a
`while`

loop which continues to iterate till`low<=high`

, i.e. till the`low`

and`high`

pointers don't cross each other indicating that the number being searched cannot be found. - Inside the
`while`

loop,`mid`

is obtained by calculating`(low+high)/2`

. - If number at position
`mid`

equals`noToSearch`

then the control returns`true`

back to`main()`

method, after printing that the number has been found along with the index at which it was found. - Else, if
`noToSearch`

is less than number at position`mid`

then the portion of the list from the mid upwards is removed from contention by making`high`

equal to`mid-1`

. - Else, it implies that
`noToSearch`

is greater than number at position`mid`

(as it is not less than and also not equal, hence, it has to be greater). Hence, the portion of the list from`mid`

and downwards is removed from contention by making`low`

equal to`mid+1`

. - The
`while`

loop continues to iterate in this way till either a`true`

value is returned (indicating`noToSearch`

has been found in the list) or`low`

becomes greater than`high`

,in which case`false`

is returned indicating that`noToSearch`

could not be found and the same is printed as output.

- Contents of the method are inside a
- Output shows a succesful search for
`68`

and an unsuccesful search for`1001`

.

Recursive Binary Search Implemention in Java

//The Class BinarySearch and its main() method are exactly the same //as in Iterative Search code, except that it calls //performBinarySearchRecursive() method here public static boolean performBinarySearchRecursive(List<Integer> integerList, Integer noToSearch, int low, int high) { if (low > high) { return false; } else { int mid = (low + high) / 2; if (integerList.get(mid).equals(noToSearch)) { System.out.println(noToSearch + " found at index " + mid); return true; } else if (noToSearch < integerList.get(mid)) { return performBinarySearchRecursive(integerList, noToSearch, low, mid - 1); } else { return performBinarySearchRecursive(integerList, noToSearch, mid + 1, high ); } } }

**Inputs - 68 & 101, and corresponding output of the above code**

68 found at index 4

1001

1001 not found

- Recursive implementation of binary search algorithm, in the method
`performBinarySearchRecursive()`

, follows almost the same logic as iterative version, except for a couple of differences. - The first difference is that the
`while`

loop is replaced by a recursive call back to the same method with the new values of`low`

and`high`

passed to the next recursive invocation along with`integerList`

and`noToSearch`

. - The second difference is that instead of returning
`false`

when the`while`

loop exits in the iterative version, in case of the recursive version, the condition of`low > high`

is checked at the beginning of the next level of recursion and acts as the boundary condition for stopping further recursive calls by returning`false`

. - Also, note that the recursive invocations of
`performBinarySearchRecursive()`

return back the search result up the recursive call stack so that`true`

or`false`

return value is passed back up the call stack without any further processing.

Summary

In the above tutorial on binary search algorithm in Java, we understood what is binary search, its steps and then saw how to implement binary search in Java recursively and iteratively.

Copyright © 2014-2016 JavaBrahman.com, all rights reserved.