[Solved] How to Implement Binary Search in Java without Recursion? Iterative Algorithm Example Tutorial

Hey Java programmers, if you want to implement a binary search in Java, and looking for both iterative and recursive binary search algorithms then you have come to the right place. Earlier, I have shared the free courses to learn Data Structure and algorithms in Java, and today, I am going to teach you an important algorithm.  In computer science, a binary search or half-interval search is a divide and conquer algorithm which locates the position of an item in a sorted array. Binary search works by comparing an input value to the middle element of the array. The comparison determines whether the element equals the input, less than the input or greater. 

When the element being compared to equals the input the search stops and typically returns the position of the element. If the element is not equal to the input then a comparison is made to determine whether the input is less than or greater than the element.

Depending on which it is the algorithm then starts over but only searching the top or a bottom subset of the array's elements. If the input is not located within the array the algorithm will usually output a unique value indicating this.

Binary search algorithms typically halve the number of items to check with each successive iteration, thus locating the given item (or determining its absence) in logarithmic time.

A binary search is a divide and conquers a search algorithm. It works by dividing the input set into half and then applying the algorithm and repeating the same steps until work is done.

Btw, if you are not familiar with fundamental search and sort algorithms, then you can also join a course like Data Structures and Algorithms: Deep Dive Using Java to learn fundamental algorithms.

If you are not a Java Programmer then, you can find more recommendations for JavaScript and Python in this list of algorithms courses.

Btw, if you prefer books, I suggest you read a comprehensive algorithm book like Grokking Algorithms by Aditya Bhargava, where he has compared liner search with binary search and how their performance and Big O time is compared.  It's one of the easiest books on Data Structure and Algorithms and I highly recommend this to all programmers.

It's also very visual and full of the useful diagram which explains the concepts well. For example, In the diagram above, you can see that when a number of elements increases, a linear search becomes slower and slower but a binary search doesn't. 

For example, for 4 billion items binary search just takes 32 guesses as opposed to the 4 billion guesses required by the linear search.

Binary Search Example in Java without Recursion

The algorithm is implemented recursively. Also, an interesting fact to know about binary search implementation in Java is that Joshua Bloch, author of the famous Effective Java book wrote the binary search in "java.util.Arrays".

import java.util.Arrays;
import java.util.Scanner;
/**
* Java program to implement Binary Search. We have implemented Iterative
* version of Binary Search Algorithm in Java
*
* @author Javin Paul
*/
public class IterativeBinarySearch {

    public static void main(String args[]) {

        int[] list = new int[]{23, 43, 31, 12};
        int number = 12;
        Arrays.sort(list);
        System.out.printf("Binary Search %d in integer array %s %n", number,
                           Arrays.toString(list));
        binarySearch(list, 12);

        System.out.printf("Binary Search %d in integer array %s %n", 43, 
                           Arrays.toString(list));
        binarySearch(list, 43);

        list = new int[]{123, 243, 331, 1298};
        number = 331;
        Arrays.sort(list);
        System.out.printf("Binary Search %d in integer array %s %n", number, 
                           Arrays.toString(list));
        binarySearch(list, 331);

        System.out.printf("Binary Search %d in integer array %s %n", 331, 
                           Arrays.toString(list));
        binarySearch(list, 1333);

        // Using Core Java API and Collection framework
        // Precondition to the Arrays.binarySearch
        Arrays.sort(list);

        // Search an element
        int index = Arrays.binarySearch(list, 3);

    }

    /**
     * Perform a binary Search in Sorted Array in Java
     *
     * @param input
     * @param number
     * @return location of element in array
     */
    public static void binarySearch(int[] input, int number) {
        int first = 0;
        int last = input.length - 1;
        int middle = (first + last) / 2;

        while (first <= last) {
            if (input[middle] &lt; number) {
                first = middle + 1;
            } else if (input[middle] == number) {
                System.out.printf(number + " found at location %d %n", middle);
                break;
            } else {
                last = middle - 1;
            }
            middle = (first + last) / 2;
        }
        if (first &gt; last) {
            System.out.println(number + " is not present in the list.\n");
        }
    }
}


Output
Binary Search 12 in integer array [12, 23, 31, 43]
12 found at location 0
Binary Search 43 in integer array [12, 23, 31, 43]
43 found at location 3
Binary Search 331 in integer array [123, 243, 331, 1298]
331 found at location 2
Binary Search 331 in integer array [123, 243, 331, 1298]
1333 is not present in the list.

That's all about how to implement binary search algorithms in Java without recursion. Like any recursive algorithm, this code doesn't use any loop like a while, for, or do-while loop. Ideally, you don't need to write code for the binary search for your day-to-day task as Java libraries already have a binarySearch() method but knowing how to write these algorithms helps in coding interviews. 


Other Data Structure and Algorithms tutorials you may like

• How to implement the Insertion sort algorithm in Java? (answer)
• 7 Best Data Structure and Algorithms Courses (best courses)
• Write a program to implement Bubble sort in Java? (solution)
• How to implement the QuickSort Algorithm in Java? (example)
• How to implement QuickSort without Recursion in Java? (example)
• How to implement the Counting Sort Algorithm in Java? (example)
• How to implement Radix Sort Algorithm in Java? (example)
• How to implement the Bucket Sort Algorithm in Java? (code)
• How to implement Merge Sort in Java? (code)
• 10 Algorithms Books Every Programmer Should Read (books)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• 100+ Data Structure Coding Problems from Interviews (questions)
• How to implement in-order traversal in Java? (solution)
• How to implement sieve of Eratosthenes algorithm in Java? (solution)
• How to implement pre-order traversal of a binary tree in Java? (solution)
• How to print all leaf nodes of a binary tree in Java? (solution)
• How to implement a binary search tree in Java? (solution)

Thanks for reading this article so far. If you like this binary search solution in Java then please share it with your friends and colleagues. If you have any questions or feedback then please drop a note.

P. S. - If you are looking for some Free Algorithm courses to improve your understanding of Data Structure and Algorithms, then you should also check the Data Structures in Java for Beginners free online course on Udemy. It's one of the best online course to learn DSA.

And lastly one question for you? what is the time and space complexity of binary search algorithm? Can you improve it by using any additional data structure?