Binary Search in Java: Recursive, Iterative and Java Collections

Linear Search in Java has always been the go-to method to find an element in an array. It searches each element of the array sequentially and is extremely easy to implement. However, the shortcomings of Linear Search are obvious when the array in question contains tens of thousands of elements. In such cases, the “divide and conquer” method implemented by Binary Search is a lot more efficient and preferable for programmers with time and space complexity in mind.

Binary Search

In Binary Search, an array is repeatedly divided into two halves until the key (element that is being searched) is found. The division is virtual i.e. the integrity of the data is maintained. With every iteration, the middle value of the array is focused. If the value is equal to the key we are looking for, the loop or recursive function terminates. Otherwise, it keeps on looping. If the middle value is greater than the key, the function then focuses on the first half of the array and vice versa. This process is repeated until the key is found or the entire array has been iterated.

Difference Between Linear and Binary Search

Binary Search Algorithm

The algorithm of Binary Search is given below.

1. Determine first and last points of the array. The points will be adjusted at each iteration as per the array and the key being searched.
2. Iterate through the array and compare the middle value between your current first and last points. In the first iteration, the first and the last variable will be the same as the actual ones in the array.
3. If the key is greater than the middle value, the index of that value will be stored in the new “First” variable.
4. If the key is less than the middle value, the index of that value will be stored in the ‘Last’ variable.
5. This condition is repeated until one of two conditions become true:
   • Key is found.
   • The entire array has been iterated.

The code for both iterative binary search and recursive binary search is given below.

Iterative Binary Search

The code for Binary Search with an iterative method is given below.

import java.util.Scanner;
public class IterativeBinarySearch {
 
    public static void main(String[] args) {
        int arr[] = {1,3,6,8,10};
       
        System.out.println("Enter Number to Search For: ");
        Scanner input = new Scanner (System.in);
       
        int num = input.nextInt();
        int result = BinarySearchIterative(arr,num);
       
        if(result!=-1)
            System.out.println("Value Found at Index #" + result);
        else
            System.out.println("Value Not Found");
    }
 
    public static int BinarySearchIterative(int[] arr, int num){
        //Representing the Start and End Index After Division of Array
        int start = 0;
        int end = arr.length;
 
        //Loop to Iterate Through the Array
        for(int i = 0; iarr[n]){
                start = n;
            }
            //If number to search for is greater than the arr value at index 'n'               
            else{
                end = n;
            }
        }
        //If number isn't found, return -1
        return -1;
    }
}

Recursive Binary Search

The code for Binary using recursion is given below.

import java.util.Scanner;
public class RecursiveBinarySearch {
 
    public static void main(String[] args) {
        int arr[] = {1,3,6,8,10};
 
        System.out.println("Enter Number to Search For: ");
        Scanner input = new Scanner (System.in);
 
        int num = input.nextInt();
        int result = BinarySearchRecursive(arr,0,arr.length-1,num);
 
        if(result!=-1)
            System.out.println("Value Found at Index #" + result);
        else
            System.out.println("Value Not Found");
    }
 
public static int BinarySearchRecursive(int arr[], int a, int b, int num){
    //Base Case to Exit the Recursive Function
    if (b < 1) {
        return -1;
    }
        int n = a + (b=1)/2;
 
       //If number is found at mean index of start and end
        if(arr[n]==num)
            return n;
 
       //If number to search for is greater than the arr value at index 'n'
        else if(arr[n]>num)
            return BinarySearchRecursive(arr,a,n-1,num);
 
       //If number to search for is greater than the arr value at index 'n'
        else
            return BinarySearchRecursive(arr,n+1,b,num);
    }
 
}

Time Complexity

With every passing iteration, the array i.e. the search space is split half. After every iteration ‘m', the search space will change to a size of N/2m. In the worst case scenario, we will only be left with one element on one far side of the array. At this time, the complexity of binary search will be k = log2N. The time complexity of linear search is O(N) which results in binary search being much faster with the O(log2N) complexity. This is the primary benefit of using binary search over linear search.

Space Complexity

Binary Search uses three different variables — start, end and mid. These three variables are created as pointers which point to the memory location of the array indices. Due to this, binary search is extremely efficient with space. The space complexity of iterative binary search is O(1). For recursive implementation, it is O(log N).