User Jesse Haniel
Jesse Haniel
Lead Software Architect at Tribunal de Justiça da Paraíba

Binary Search in Java: Recursive, Iterative and Java Collections

Published in the Java Developer group
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.Binary Search in Java: Recursive, Iterative and Java Collections - 1

Difference Between Linear and Binary Search

Linear Search Binary Search
Sequentially searches the array Divides the array into two halves until the value is found
Works with any array Works only with sorted arrays
Complexity is O(N) Complexity is O(log2N)
Can work on sorted and unsorted arrays Can only be implemented on sorted arrays.
Less complex to implement More complex to implement

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.Binary Search in Java: Recursive, Iterative and Java Collections - 2

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).
Comments (2)
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION
Jonaskinny Level 25, Redondo Beach, United States
20 February 2022
first example code does not compile, is incomplete. Concept is straight forward, but would be better to provide executable code so students can play with it to better understand.
Dennis Level 16, Bridgeport, USA
23 October 2020
Bookmarking this info so I can re-read it a 100 times. Good stuff!