How Binary Search Algorithm Works? Java Example without Recursion

The binary search algorithm is one of the fundamental Computer Science Algorithms and is used to search an element in a sorted input set. It’s much faster than the linear search which scans each and every element and improves performance from O(n) to O(logN) for searching an element in the array. In order to perform the binary search, you need a sorted array, so you can either ask the user to enter the array in sorted order or you should sort the array before performing the binary search. It’s also one of the popular algorithms for Programming Job interviews. The interviewer often asks candidates to implement binary search algorithms by hand in their favorite programming languages like Java, C++, Python. or JavaScript.

Since Binary Search can be easily implemented using Recursion, sometimes they also test candidates by asking them to implement binary search without recursion, also known as an iterative binary search algorithm.

In this article, we will write a Java program that will take input from the user, both array and the number to be searched, and then perform a binary search to find that number in a given array.

You’ll not use the Collections.binarySearch() method instead we’ll write our own because it’s a programming exercise to test one’s coding skill. In order to implement a binary search, you must first know how binary search works? If you don’t know the algorithm you cannot code it. So, let’s first revise the binary search algorithm itself.

How Binary Search Algorithm works? Example

If you remember something about searching algorithms from your data structure and algorithms classes from your Computer Science degree college days you might know that binary search works on the principle of divide and conquer.

In this technique, a solution is found by dividing the input into smaller sets using some rules.

In a binary search algorithm, you first find the middle element of the array and compare that with the number you are searching for. If it’s equal then you return true or index of that number and your binary search is complete but if it doesn’t match then you divide the array in two-part based upon whether the middle element is greater than or less than the key value, which you are searching.

If the key(target value) is greater than the middle element then search values in the second half of the array because the array is sorted in increasing order. Similarly, if the key is lower than the middle element it means it’s in the first part of the array.

After each iteration, you rule out half of the array elements. This means if you have 100 elements in the array then you need O(log2 100) i.e. 10 iterations to actually find the value or confirm that it doesn’t exist in the array.

If you are not sure about how to calculate the time and space complexity of an algorithm, you should refer to a good data structure and algorithm course like Algorithms and Data Structures – Part 1 and 2 on Pluralsight.  It’s essential from the interview point of view to be able to find out the time and space complexity of an algorithm.

Several important data structures like binary search tree and binary heap are based upon the binary search algorithm, that’s why it is very important for a programmer or Computer Science graduate to understand and implement this algorithm by hand.

Binary search is naturally a recursive algorithm because what you are doing is essentially a binary search at smaller input after each iteration, but in this program, you’ll implement binary search without recursion.

This is to prepare you well for your interviews because often Interviewer asks the candidate to write both iterative and recursive solutions to a problem like

Here is also a flowchart of the binary search algorithm, which will explain what I said more clearly, remember one picture is worth more than 1000 words.

How to implement Binary Search in Java

Here is our implementation of the popular binary search algorithm in Java.  However, you don’t need to implement this algorithm if you want to use it in your production code. JDK collection API already has a binarySearch() method on the java.util.Arrays class.  This implementation is for educational and for interview preparation purposes to teach students how to code binary search in Java.

import java.util.Scanner;

/*
 * Java Program to implement binary search without using recursion
 */
public class BinarySearch {

    public static void main(String[] args) {

        Scanner commandReader = new Scanner(System.in);
        System.out.println("Welcome to Java Program to perform 
                               binary search on int array");
        System.out.println("Enter total number of elements : ");
        int length = commandReader.nextInt();
        int[] input = new int[length];

        System.out.printf("Enter %d integers %n", length);
        for (int i = 0; i < length; i++) {
            input[i] = commandReader.nextInt();
        }

        System.out.println("Please enter number to be searched in array 
                                    (sorted order)");
        int key = commandReader.nextInt();

        int index = performBinarySearch(input, key);

        if (index == -1) {
            System.out.printf("Sorry, %d is not found in array %n", key);
        } else {
            System.out.printf("%d is found in array at index %d %n", key,
                                                         index);
        }

        commandReader.close();

    }

    /**
     * Java method to perform binary search. It accept an integer array and a
     * number and return the index of number in the array. If number doesn't
     * exists in array then it return -1
     *
     * @param input
     * @param number
     * @return index of given number in array or -1 if not found
     */
    public static int performBinarySearch(int[] input, int number) {
        int low = 0;
        int high = input.length - 1;

        while (high >= low) {
            int middle = (low + high) / 2;
            if (input[middle] == number) {
                return middle;
            } else if (input[middle] < number) {
                low = middle + 1;
            } else if (input[middle] > number) {
                high = middle - 1;
            }
        }
        return -1;
    }

}


Output
Welcome to Java Program to perform binary search on int array
Enter total number of elements : 
4
Enter 4 integers 
10
20
20
34
Please enter number to be searched in array
34
34 is found in array at index 3 

Welcome to Java Program to perform binary search on int array
Enter total number of elements : 
7
Enter 7 integers 
1
2
3
4
5
6
7
Please enter number to be searched in array
10
Sorry, 10 is not found in array 

You can see that in our first array which is sorted 34 is successfully searched, but when I enter another number that is not in the array, you can see it successfully says that element is not in the array.

That’s all about how to implement binary search in Java without using recursion. This is an iterative solution to the binary search problem. The time complexity of the binary search is in order of O(logN) if you get the sorted input. If you have to sort the input then you need to add that time to the total run time of the algorithm as well.