Iterative Binary Search Algorithm in Java

Binary Search is one of the most effective search algorithms used for searching a list of sorted items.

Known complexities for average, best and worst cases are considered as follows :

Worst case performance       =  O(log n)
Best case performance          =  O(1)
Average case performance   =  O(log n)

Following is the iterative implementation of binary search algorithm in Java.

package basics;

import java.util.Arrays;

public class IterativeBinarySearch {
 
 public static int index( int[] input, int key )
 {
    int low = 0;
    int high = input.length-1;  
    while( low<=high )
    {
       int mid = low+(high-low)/2;
       if( key<input[mid] )
          high = mid-1;
       else if( key>input[mid] )
          low = mid+1;
       else
          return mid;
    }
    return -1;
 }
 
 public static void main(String[] args) {
  
  int[] list = {22,55,66,11,32,56,67,89,95,10};
  
  Arrays.sort(list);
  
  int itemIndex = index(list, 22);
  System.out.println(itemIndex);
  
  itemIndex = index(list, 11);
  System.out.println(itemIndex);
  
  itemIndex = index(list, 67);
  System.out.println(itemIndex);
  
  itemIndex = index(list, 10);
  System.out.println(itemIndex);

  itemIndex = index(list, 101);
  System.out.println(itemIndex);
 }
 
}

Create a IterativeBinarySearch.java file in your workspace.

When the main method inside the IterativeBinarySearch class executed it is going to print :

2
1
7
0
-1