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.

Btw, If you are new to data structure and algorithms then I also suggest you join a comprehensive course like Data Structures and Algorithms: Deep Dive Using Java course on Udemy, which will not only teach you the binary search algorithms but also other essential data structures and graph and hash-based algorithms.

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

• Iterative and Recursive way to reverse String (check here)
• Printing Fibonacci series with and without recursion (see here)
• Finding the length of the linked list using iteration and recursion (see here)
• Pre Order traversal on a binary tree using both recursion/iteration (click here)
• Post Order traversal on a binary tree using both recursion/iteration (click here)
• In Order traversal on a binary tree using both recursion/iteration (click here)

If you need more questions for practice for your coding interviews then you can also check out the Cracking the Coding Interview - 189 Questions and Solutions book, which contains more than 189 Coding problems and their solutions.

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.



Other Array-based coding problems for Interviews:

• How to implement a quicksort algorithm without recursion in Java? (solution)
• Difference between Quicksort and Counting Sort Algorithm? (answer)
• How to remove an element from an array in Java? (solution)
• How to find duplicates from an unsorted array in Java? (solution)
• 10 Algorithms Books Every Programmer Should Read (books)
• 50+ Data Structure and Algorithms Problems from Interviews (questions)
• Difference between Counting Sort and Bucket Sort Algorithm? (answer)
• How to find all pairs in an array whose sum is equal to k (solution)
• How to reverse an array in place in Java? (solution)
• Difference between Quicksort and Mergesort Algorithm? (answer)
• Some Free courses to learn data Structure in-depth (FreeCodeCamp)
• How to find a missing value from an array containing 1 to 100? (solution)
• How to count the number of leaf nodes in a given binary tree in Java? (solution)
• Recursive InOrder traversal Algorithm (solution)
• 10 Free Data Structure and Algorithm Courses for beginners (free courses)
• 100+ Data Structure Coding Problems from Interviews (questions)
• How to remove duplicates from an array in Java? (solution)

Thanks for reading this article so far. If you like this Java Array tutorial then please share it with your friends and colleagues. If you have any questions or feedback then please drop a comment.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check these free Algorithms courses on Udemy. It's authored by a Google Software Engineer and Algorithm expert and it's completely free of cost.

P. S. S. - If you have not read it already then you should also read Introduction to Algorithms by Thomas H. Cormen to learn more about Algorithms and Data Structure.