How to code an iterative binary search algorithm in Java

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

Yes, you guessed it right: you need to implement a binary search in Java and you need to write both iterative and recursive binary search algorithms.

Algorithm

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 sort. Binary searching works by comparing an input value to the middle element of the array.

The comparison determines if 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 if 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 that is 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 take a course like Data Structures in Java: An Interview Refresher to learn fundamental algorithms.

How to code Iterative Binary Search in Java

Here is some sample code that shows the logic behind iterative binary search in Java. After that, we will use the same method to search an array using Iterative binary search:

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");
      }
   }
}

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 will learn in your computer science class.

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.

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

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)