Binary Search in Java

Binary Search in Java | Binary search is an efficient algorithm for finding an item from a sorted list or array of items. Sometimes it is also known as half-interval search, logarithmic search, or binary chop. 

Condition to use the binary search:- The array must be sorted in ascending order.

The binary search algorithm cannot be applied to unsorted arrays. This algorithm can be used when the array has terms occurring in order of increasing size (for instance: if the terms are numbers, they are listed from smallest to largest; if they are words, they are listed in lexicographic, or alphabetic, order). If the array or list is not sorted then before applying the binary search algorithm, first sort the array or list.

The binary search algorithm can be written in two ways. These are,
a) Recursive approach
b) Iterative approach

Table of contents

• Binary Search in Java using Recursion
  • Binary Search Algorithm in Java using Recursion
  • How Recursive approach works?
  • Java Program to implement binary search using Recursion
• Binary Search in Java using Iterative approach
  • Algorithm
  • Java Program
• Arrays.binarySearch() Method in Java
  • Example using Arrays.binarySearch()
• Binary Search Time Complexity

Binary Search in Java using Recursion

In the recursive approach, the recursion technique is used. It is an example of the divide and conquers technique where bigger problems are divided into smaller problems. Like all divide and conquer algorithms binary search first divide the large array into smaller sub-arrays and then solve it recursively.  We will see it in detail.

Binary Search Algorithm in Java using Recursion

a) Take an array, initial index, size, and search key.
b) Find the middle term.
c) If middle term == search key then return index.
d) If middle term > search key then apply recursive call on the first half of the array.
e) Else apply recursive call on the second half of the array.
f) Repeat the process until the search key is not matched.
g) If not matched then return -1.

The binary search method in java using recursion can be written as,

int binarySearch(arr, low, high, key) {
   if (high >= low) {
      int mid = low + (high - low) / 2; 
      if (arr[mid] == key) return mid; 
      if (arr[mid] > key) 
         return binarySearch(arr, low, mid - 1, key); 
      return binarySearch(arr, mid + 1, high, key); 
   }
   return -1; 
}

The time complexity of this algorithm = O(log n)

How Recursive Approach for Binary Search works?

In binary search using the recursive approach, we split the array from the middle into two subarrays of the same size or where one of these smaller lists has one fewer term than the other. Let us understand it through an example.

Array = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};

Example

Assume the search term = 40. Then the steps in binary search,

1. Find the middle term of the array. If the size of array is odd then middle-index = (size – 1)/2 else middle-index = size/2. In our example, middle index = 10/2 = 5, and middle term is array[3] = 60
2. Compare middle term and search term. If the middle term > search term then it may exist in the first portion of the array else in the second portion of the array. Since 60 > 40 therefore search term may exist only in the first portion of the array.
3. Split the array into two parts from the middle index. The subarr1 = {10, 20, 30, 40, 50} and subarr2 = {60, 70, 80, 90, 100}.
4. Since the array is sorted and 60 > 40, therefore search terms may exist only in the first sub-array. Forgot about the second sub-array, no use of it, only the first sub-array is required for the next step. Now, assume the original array = {10, 20, 30, 40, 50}, and search term = 40.
5. Repeat the same process with first sub array. Find the middle term. The middle index = (5-1)/2 = 2, middle term is array[2] = 30
6. Compare middle term with the search term, 30 < 40 therefore it may exist only in the second portion.
7. Split array into two subarrays from the middle index. The new sub arrays are:- subarr1 = {10, 20} and subarr2 = {30, 40, 50}. Only subarr2 will be considered for the next steps, no use of subarr1. Now, assume array = {30, 40, 50} and search term = 40. Repeat the process.
8. Find middle term. The middle index = (3-1)/2 = 1 and the middle term is array[1] = 40.
9. Compare middle term and search term. Currently, both are equal and the match is found.

Java Program to Implement Binary Search Using Recursion

Now let us see the implementation of the binary search algorithm in the Java programming language. Here the method binarySearch() finds the index of the search key, if the match is found then it returns the index of the search key else it returns -1.

public class Search {

   public static void main(String[] args) {
      int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
      int key = 40; // search key

      // binary search
      int index = binarySearch(arr, 0, arr.length, key);

      // display result
      if (index == -1)
         System.out.println(key + " not Found.");
      else
         System.out.println(key + " Found at Index = " + index);
   }

   // Method for binary search
   /* if match found then return index of search key
      else return -1 */
   public static int binarySearch(int[] arr, int low,
                           int high, int key) {
      if (high >= low) {
         // find middle index
         int mid = low + (high - low) / 2; 
     
         // find middle term and compare
         if (arr[mid] == key) return mid; // key found 
     
         // If key is smaller than middle term, then 
         // it can only be present in left subarray 
         if (arr[mid] > key) 
            return binarySearch(arr, low, mid - 1, key); 
     
         // Else the key can only be present 
         // in right subarray 
         return binarySearch(arr, mid + 1, high, key); 
      } 
     
      // key not found
      return -1; 
   }

}

Output:-

40 Found at Index = 3

Binary Search in Java using Iterative approach

In this approach, instead of calling the method recursively, we use iteration to traverse the array and find the search key. Both approaches are quite the same, with two differences in implementation. 

In the recursive method, there is no loop, and rather than passing the new values to the next iteration of the loop, it passes them to the next recursion. In the iterative method, the iterations can be controlled through the looping conditions, while in the recursive method, the maximum and minimum are used as the boundary condition. 

Algorithm for Binary Search in Java using Iterative approach

To search for the integer x in the list/array a₁, a₂ , … ,a_n , where array is in ascending order (a₁ < a₂ <  ··· < a_n) , 

• begin by comparing x with the middle term a_m of the list/array, where m = ⌊(n + 1)/2⌋. 
• If x > a_m, the search for x is restricted to the second half of the list, which is a_m+1, a_m+2, …, a_n.
• If x is not greater than a_m, the search for x is restricted to the first half of the list, which is a₁, a₂, …, a_m.
• The search has now been restricted to a list with no more than ⌊n/2⌋ elements. 
• Using the same procedure, compare x to the middle term of the restricted list. 
• Then restrict the search to the first or second half of the list. 
• Repeat this process until a list with one term is obtained. 
• Then determine whether this term is x.

The algorithm can be written as,

int binary search (a: array, lowIndex, highIndex,  x: search-key) {
   i = lowIndex; // i is left endpoint of search interval
   j = highIndex; // j is right endpoint of search interval
   while (i < j) {
      m = (i+j)/2; // floor of (i+j)/2
      if (x > a[m] ) then i = m+1;
      else j = m;
   }
   if (x=a[i]) then location = i;
   else location = -1;
   return location'
}

Program for Binary Search in Java using Iterative approach

Now let us see the Java program for binary search using the iterative approach,

import java.util.Scanner;

public class Search {

  public static void main(String[] args) {
    // Scanner class object to read input
    Scanner scan = new Scanner(System.in);

    // array
    int arr[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };

    // read search key
    System.out.print("Enter search key: ");
    int key = scan.nextInt();

    // binary search
    int index = binarySearch(arr, key);

    // display result
    if (index == -1)
      System.out.println(key + " not Found.");
    else
      System.out.println(key + " Found at Index = " + index);
    
    // close Scanner class object
    scan.close();

  }

  // binary search for complete array
  public static int binarySearch(int[] arr, int key) {
    // pass 0 as low value, array-size as high value
    return binarySearchRange(arr, 0, arr.length, key);
  }

  // Binary search method for a given range of array
  /* if match found then return index of 
   * search key else return -1
   */
  public static int binarySearchRange(int[] arr, 
                         int low, int high, int key) {
    int i = low; // left index
    int j = high; // right index
    int mid = 0;

    while (i < j) {
      // find middle index
      mid = (i + j) / 2;

      // compare search key and middle term
      if (key > arr[mid])
        i = mid + 1;
      else
        j = mid;
    }

    // when i==j
    if (key == arr[i])
      return i; // key found
    return -1; // key not found
  }
}

Output:-

Enter search key: 50
50 Found at Index = 4

Enter search key: 88
88 not Found.

Arrays.binarySearch() Method in Java

While working with the Java programming language, no need to write the separate logic for the binary search algorithm. In java.util.Arrays class we have an in-built method called binarySearch(). The Java Arrays class was introduced in JDK 1.2 version, which contains various methods for manipulating arrays such as sorting, searching, copying, converting an array to string and e.t.c. 

The Arrays.binarySearch() method searches the specified array for the specified value using the binary search algorithm. It uses an iterative approach, not the recursive method.

Condition to use the Arrays.binarySearch() method:- The array must be sorted in ascending order. If the array is not sorted, the results will be undefined.

If the array is not sorted then we can use Arrays.sort() or Arrays.parallelSort() to sort the given array in ascending order. If the array contains multiple elements with the specified value, there is no guarantee which one will be found.

There are several overloaded forms of binarySearch() method either with range or without range.

• public static int binarySearch(byte[] a, byte key)
• public static int binarySearch(short[] a, short key)
• public static int binarySearch(int[] a, int key)
• public static int binarySearch(long[] a, long key)
• public static int binarySearch(float[] a, float key)
• public static int binarySearch(double[] a, double key)
• public static int binarySearch(char[] a, char key)
• public static int binarySearch(Object[] a, Object key)
• public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
• public static int binarySearch(byte[] a, int fromIndex, int toIndex, byte key)
• public static int binarySearch(short[] a, int fromIndex, int toIndex, short key)
• public static int binarySearch(int[] a, int fromIndex, int toIndex, int key)
• public static int binarySearch(long[] a, int fromIndex, int toIndex, long key)
• public static int binarySearch(float[] a, int fromIndex, int toIndex, float key)
• public static int binarySearch(double[] a, int fromIndex, int toIndex, double key)
• public static int binarySearch(char[] a, int fromIndex, int toIndex, char key)
• public static int binarySearch(Object[] a, int fromIndex, int toIndex, Object key)
• public static <T> int binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c)

Parameters in binarySearch() method:-

• a:- the array to be searched
• fromIndex:- the index of the first element (inclusive) to be searched
• toIndex:- the index of the last element (exclusive) to be searched
• key:- the value to be searched for

Return value:- It returns the index of the search key. If the array doesn’t contain a key then it returns -1.

Internally they call the binarySearch0() method which is implemented using an iterative approach as follows:-

private static int binarySearch0(long[] a, int fromIndex, int toIndex,
                                     long key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        long midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

Example Using Arrays.binarySearch()

Example Using Arrays.binarySearch() of Java Arrays class to search an element in a given sorted array,

import java.util.Arrays;

public class Search {
  public static void main(String[] args) {

    // array
    int arr[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };

    // search 85
    System.out.println("80 found at index = " 
                    + Arrays.binarySearch(arr, 80) );

    // search 75
    if (Arrays.binarySearch(arr, 75) != -1) {
      System.out.println("75 Found");
    } else {
      System.out.println("75 not Found");
    }
  }
}

Output:-

80 found at index = 7
75 Found

If the array is not sorted in ascending order then we may get the wrong result. If the array is sorted but in descending order then also we may get the wrong result.

import java.util.Arrays;

public class Search {
  public static void main(String[] args) {

    // array
    int arr[] = { 100, 20, 30, 10, 50};

    // search 20
    System.out.println("20 found at index = " 
                       + Arrays.binarySearch(arr, 20));
  }
}

Output:-

20 found at index = -1

Therefore, if array is not sorted then before calling Arrays.binarySearch() method, sort the given array with the help of Arrays.sort() or Arrays.parallelSort(). See:- How to sort an array in Java

import java.util.Arrays;

public class Search {
  public static void main(String[] args) {

    // array
    int arr[] = { 100, 20, 30, 10, 50};
    
    // display intial array
    System.out.println("Initial array = " 
                       + Arrays.toString(arr));
    
    // sort the array
    Arrays.sort(arr);
    
    // display array after sorting
    System.out.println("Array after Sorting= "  
                       + Arrays.toString(arr));

    // search 20
    System.out.println("20 found at index = "  
                       + Arrays.binarySearch(arr, 20));
  }
}

Output:-

Initial array = [100, 20, 30, 10, 50]
Array after Sorting = [10, 20, 30, 50, 100]
20 found at index = 1

In this program, to display the array we have used the Arrays.toString() method which is given to convert the array to string.

Let us see one more Java program example using a binary search algorithm. Now, we don’t write the logic for the binary search algorithm. Instead, we will call the Arrays.binarySearch() method and if required then first we will sort the given array.

Program Description:- Write a Java program to search a String from the list of Strings by using a binary search algorithm.

import java.util.Arrays;
import java.util.Scanner;

public class Search {
  public static void main(String[] args) {

    // unsorted array of String
    String arr[] = {"Java", "HTML", "C++", "Python", "CSS"};
    
    // display initial array
    System.out.println("Initial array = " 
                       + Arrays.toString(arr));
    
    // sort the array
    Arrays.sort(arr);
    
    // display array after sorting
    System.out.println("Initial array = " 
                       + Arrays.toString(arr));

    // Scanner class object to read input
    Scanner scan = new Scanner(System.in);
    
    // read character
    System.out.print("Enter a string to search: ");
    String str = scan.next();
    
    // search character
    int index = Arrays.binarySearch(arr, str);
    
    // display result
    if(index != -1)
      System.out.println(str + " found at index = " + index);
    else
      System.out.println(str+" not found.");
    
    // close Scanner
    scan.close();
  }
}

Output:-

Initial array = [Java, HTML, C++, Python, CSS]
Initial array = [C++, CSS, HTML, Java, Python]
Enter a string to search: Java
Java found at index = 3

Initial array = [Java, HTML, C++, Python, CSS]
Initial array = [C++, CSS, HTML, Java, Python]
Enter a string to search: C#
C# not found.

Binary Search Time Complexity

Best-case time complexity	O(1)	When the search key present at the center (middle term) of the array.
Worst-case time complexity	O(log n)	When the search key is not available or at the extremity of the list.

In the iterative method, the space complexity would be O(1). While in the recursive method, the space complexity would be O(log n). 

For the small arrays linear search algorithm gives better performance compared to the binary array, but for the large arrays if the array is in sorted order then the binary search gives better performance compared to the linear search. 

There are specialized data structures designed for fast searching, such as hash tables, that can be searched more efficiently than binary search. However, binary search can be used to solve a wider range of problems, such as finding the next-smallest or next-largest element in the array relative to the target even if it is absent from the array.

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Search