Recursive 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 recursive implementation of binary search algorithm in Java.

package basics;

import java.util.Arrays;

public class RecursiveBinarySearch {

 public static int index( int[] input, int key )
 {
     return index( input, key, 0, input.length-1 );
 }
 
 public static int index( int[] input, int key, int low, int high )
 {
     if( low>high )
         return -1;
  
     int mid = low+(high-low)/2;
  
     if( key>input[mid] )
         return index(input, key, mid+1, high);
     else if( key<input[mid] )
         return index( input, key, low, mid-1 );
     else
         return mid;
 }
 
 public static void main(String[] args) {
  
  int[] list = {22,55,66,11,32,56,67,89,95,10};
  
  Arrays.sort(list);
  
  System.out.print("Sorted Array = ");
  for (int i = 0; i < list.length; i++) {
   System.out.print(list[i]+" ");
  }
  
  int itemIndex = index(list, 22);
  System.out.println("\n\nItem = "+22+", Index = "+itemIndex);
  
  itemIndex = index(list, 11);
  System.out.println("Item = "+11+", Index = "+itemIndex);
  
  itemIndex = index(list, 67);
  System.out.println("Item = "+67+", Index = "+itemIndex);
  
  itemIndex = index(list, 10);
  System.out.println("Item = "+10+", Index = "+itemIndex);

  itemIndex = index(list, 101);
  System.out.println("Item = "+101+", Index = "+itemIndex);
  
 }
}

Create a RecursiveBinarySearch.java file in your workspace.

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

Sorted Array = 10 11 22 32 55 56 66 67 89 95

Item = 22, Index = 2
Item = 11, Index = 1
Item = 67, Index = 7
Item = 10, Index = 0
Item = 101, Index = -1