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
high are initialized to the first and the last elements of
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
'mid'position is equals
'e', then the element to be searched is declared found and the iteration along with the algorithm ends.
- STEP 2: If element at
'mid'is found not equal to
'e'in STEP 1, then it is checked whether
'e'is less than element at
'mid'. If yes, then
'high'is set to the position
'low'remains as it is. The iteration ends and control moves back to STEP 1.
- STEP 3:
'e'is now determined to be greater than element at
'low'is set to the position
'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
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
BinarySearchclass starts off with defining a list of integers of size
- Next the number to be searched is taken as input from the user using a
Scannerinstance, and stored in
- The key pointers to
highare assigned values of
integerList.size() - 1has value
performBinarySearchIterative()method is invoked with
performBinarySearchIterative()does the following -
- Contents of the method are inside a
whileloop which continues to iterate till
low<=high, i.e. till the
highpointers don't cross each other indicating that the number being searched cannot be found.
- Inside the
midis obtained by calculating
- If number at position
noToSearchthen the control returns
main()method, after printing that the number has been found along with the index at which it was found.
- Else, if
noToSearchis less than number at position
midthen the portion of the list from the mid upwards is removed from contention by making
- Else, it implies that
noToSearchis 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
midand downwards is removed from contention by making
whileloop continues to iterate in this way till either a
truevalue is returned (indicating
noToSearchhas been found in the list) or
lowbecomes greater than
high,in which case
falseis returned indicating that
noToSearchcould not be found and the same is printed as output.
- Contents of the method are inside a
- Output shows a succesful search for
68and an unsuccesful search for
Recursive Binary Search Implemention in Java
- 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
whileloop is replaced by a recursive call back to the same method with the new values of
highpassed to the next recursive invocation along with
- The second difference is that instead of returning
whileloop exits in the iterative version, in case of the recursive version, the condition of
low > highis checked at the beginning of the next level of recursion and acts as the boundary condition for stopping further recursive calls by returning
- Also, note that the recursive invocations of
performBinarySearchRecursive()return back the search result up the recursive call stack so that
falsereturn value is passed back up the call stack without any further processing.
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.