Iterative Binary Search Algorithm for Coding Interviews

Disclosure: This post includes affiliate links; I may receive compensation if you purchase products or services from the different links provided in this article.

Hello everyone! I have published a lot of algorithms and data structure articles from coding interviews on my blog, but this one is one of the first ones here. In this article, we'll examine popular fundamental algorithms for interviews.

Yes, you guessed it right: I am talking about binary search algorithm, one of the fundamental search algorithm which is neither too easy nor too tough. This algorithm is very easy to implement with Recursion and that's why most of the interviewer will force you to implement a binary search algorithm without recursion, also known as iterative binary search and that's what you will learn in this tutorial.

In computer science, a binary search, or half-interval search, is a divide and conquer algorithm that locates the position of an item in a sorted array. Binary searching works by comparing an input value to the middle element of the array.

The comparison determines whether the element equals the input, is less than the input, or is greater than the input.

When the element being compared 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 the result, the algorithm then starts over again, 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 like -1 or just throw a RuntimeException in Java like NoValueFoundException.

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.

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 Java is not your choice of language, 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 Introduction to Algorithms by Thomas H. Cormen.

Here is some sample code that shows the logic of iterative binary search in Java:

Binary Search without Recursion in Java

Here is a sample program to implement binary search in Java. 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] < 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 > 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 without using recursion in Java. Along with Linear search, these are two of the essential search algorithms you should have learned in your computer science class.

These are not just important from a Coding interview perspective but also to understand other essential data structures like binary search tree or BST.

The binary search tree data structure takes advantage of this algorithm and arranges data in a hierarchical structure so that you can search any node in O(logN) time.

Though, you must remember that in order to use binary search, you need a sorted list or sorted array, so you also need to consider the cost of sorting when you consider using binary search algorithms in the real world.

Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures --- Part 1 and 2
Data Structures in Java 9 by Heinz Kabutz
10 Algorithms books for Interviews
10 Data Structure and Algorithm Courses for Interviews
5 Free Courses to Learn Data Structure and Algorithms
Data Structures in Java: An Interview Refresher

Other Data Structure and Algorithms Problems from Programming Job interviews

• How to implement the Quicksort algorithm in place in Java? (tutorial)
• How to implement Binary Search Tree in Java? (solution)
• How to implement Quicksort algorithm without recursion? (tutorial)
• How to implement the Insertion sort algorithm in Java? (tutorial)
• How to implement a Bubble sort algorithm in Java? (tutorial)
• What is the difference between Comparison and Non-Comparison based sorting algorithms? (answer)
• How to implement Bucket Sort in Java? (tutorial)
• How to implement a Binary Search Algorithm without recursion in Java? (tutorial)
• 50+ Data Structure and Algorithms Courses for Programmers (questions)

Thanks for reading this article. If you like this article then please share it with your friends and colleagues. If you have any suggestions or feedback then please drop a comment.

P.S. - If you are serious about improving your Algorithm skills, I think the Data Structures and Algorithms: Deep Dive Using Java is the best one to start with.