Java Program to Perform Binary Search in Array without Recursion

The binary search algorithm is used to search an element in the sorted array. It's faster than linear search 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 array in sorted order or you should sort the array before performing the binary search. In this article, we will write a Java program which 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 given array. We'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 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

If you remember something about searching algorithms from your data structure and algorithm classes in Engineering college 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 on some rules.

In binary search algorithm, you first find the middle element of the array and compare that with the number you are searching. 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 is greater than middle element than search values in the second half of array because the array is sorted in increasing order. Similarly, if the key is lower than middle element it means it's in the first part of the array.

After each iteration you rule out half of array elements. Which 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 time and space complexity of an algorithm, you should refer to a good data structure and algorithm book like Introduction to Algorithms by Thomas Cormen. It's essential from the interview point of view to be able to find out time and space complexity of any algorithm.

Binary search in Java without recursion


Several important data structure e.g. binary search tree and binary heap are based upon the binary search algorithm, that's why it becomes very important for any programmer 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, we'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 solution of a problem e.g.

  • Iterative and Recursive way to reverse String (check here)
  • Printing Fibonacci series with and without recursion (see here)
  • Finding length of linked list using iteration and recursion (see here)


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

flowchart of binary search algorithm in Java


How to implement Binary Search in Java

Here is our implementation of the popular binary search algorithm in Java.  Though, 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 Arrays class. This implementation is for educational purpose 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 

That's all about how to implement binary search in Java without using recursion. This is an iterative solution of the binary search problem. The time complexity of 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 on the total run time of the algorithm as well. If you have not read already then you should read Introduction to Algorithms to learn more about how to calculate time and space complexity of an algorithm.


No comments:

Post a Comment