JB Header
Iterative and Recursive Binary Search Algorithm Implementation in Java
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 '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 'mid-1' while '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 'mid'. Pointer '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
Iterative Binary Search Algorithm 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
68 found at index 4

1001
1001 not found
Explanation of the code & output
  • 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.
  • Output shows a succesful search for 68 and an unsuccesful search for 1001.
Recursive Binary Search Implemention in Java
Recursive Binary Search Algorithm 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
68 found at index 4

1001
1001 not found
Explanation of the code & output
  • 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.