Static Generic Recursive Binary Search Algorithm In Java

Binary Search algorithm can be implemented recursively in a generic way in Java.

Generic recursive binary search method accepts input parameters as any item that implements Comparable interface.

Static binary search method was tested with Integer, Double and String type of parameters where each of them individually implements Comparable interface.

package basics;

import java.util.Arrays;

public class GenericRecursiveBinarySearch {

  public static <T extends Comparable<T>> int index( T[] items, T item )
  {
      return index( items, item, 0, items.length-1 );
  }
  
  public static <T extends Comparable<T>> int index( T[] items, T key, int low, int high )
  {
      if ( key == null )
          return -1;
   
      if( low > high  )
          return -1;
    
      int mid = low+(high-low)/2;
    
      if( key.compareTo( items[mid] ) > 0 )
          return index(items, key, mid+1, high);
      else if( key.compareTo( items[mid] ) < 0 )
          return index( items, key, low, mid-1 );
      else
          return mid;
  }  

  public static void main(String[] args) {

      Integer[] items = { 22, 55, 66, 11, 32, 56, 67, 89, 95, 10 };

      Arrays.sort(items);
      System.out.print("Sorted Integer Array = ");
      for (Integer item : items) {
           System.out.print(item+" ");
      }
  
      int foundIndex = index(items, Integer.valueOf(22));
      System.out.println("\nInteger Array Contains item 22 at index = " + foundIndex);

      foundIndex = index(items, Integer.valueOf(11));
      System.out.println("Integer Array Contains item 11 at index = " + foundIndex);

      foundIndex = index(items, Integer.valueOf(67));
      System.out.println("Integer Array Contains item 67 at index = " + foundIndex);

      foundIndex = index(items, Integer.valueOf(10));
      System.out.println("Integer Array Contains item 10 at index = " + foundIndex);

      foundIndex = index(items, Integer.valueOf(101));
      System.out.println("Integer Array Contains item 101 at index = " + foundIndex);

      foundIndex = index(items, null);
      System.out.println("Integer Array Contains item null at index = " + foundIndex);

      String[] strItems = { "alk", "abc", "adk", "zyt", "fre", "nhy" };
      Arrays.sort(strItems);

      System.out.print("\nSorted String Array = ");
      for (String item : strItems) {
           System.out.print(item+" ");
      }
  
      foundIndex = index(strItems, "alk");
      System.out.println("\nString Array Contains item alk at index = " + foundIndex);

      foundIndex = index(strItems, "nhy");
      System.out.println("String Array Contains item nhy at index = " + foundIndex);

      foundIndex = index(strItems, "zyt");
      System.out.println("String Array Contains item zyt at index = " + foundIndex);

      foundIndex = index(strItems, "zyts");
      System.out.println("String Array Contains item zyts at index = " + foundIndex);

      foundIndex = index(strItems, "null");
      System.out.println("String Array Contains item null at index = " + foundIndex);

      Double[] dItems = { 11.3, 13.3, 6.0, 9.6, 45.7, 23.2 };
      Arrays.sort(dItems);

      System.out.print("\nSorted Double Array = ");
      for (Double item : dItems) {
           System.out.print(item+" ");
      }
  
      foundIndex = index(dItems, 13.3);
      System.out.println("\nDouble Array Contains item 13.3 at index = " + foundIndex);

      foundIndex = index(dItems, 14.3);
      System.out.println("Double Array Contains item 14.3 at index = " + foundIndex);

      foundIndex = index(dItems, 23.0);
      System.out.println("Double Array Contains item 23.0 at index = " + foundIndex);

 }
}

Binary search works for sorted arrays so before calling binary search on arrays call Arrays.sort to sort array items.

Create a GenericRecursiveBinarySearch.java file in your workspace.

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

Sorted Integer Array = 10 11 22 32 55 56 66 67 89 95
Integer Array Contains item 22 at index = 2
Integer Array Contains item 11 at index = 1
Integer Array Contains item 67 at index = 7
Integer Array Contains item 10 at index = 0
Integer Array Contains item 101 at index = -1
Integer Array Contains item null at index = -1

Sorted String Array = abc adk alk fre nhy zyt
String Array Contains item alk at index = 2
String Array Contains item nhy at index = 4
String Array Contains item zyt at index = 5
String Array Contains item zyts at index = -1
String Array Contains item null at index = -1

Sorted Double Array = 6.0 9.6 11.3 13.3 23.2 45.7
Double Array Contains item 13.3 at index = 3
Double Array Contains item 14.3 at index = -1
Double Array Contains item 23.0 at index = -1

Static Generic Iterative Binary Search Algorithm In Java

In order take advantage of Generics in Java, binary search method can be implemented generically.

Binary search works for sorted Arrays so Arrays.sort method is used before using binarySearch method.

Any type that implements Comparable interface is accepted by the generic iterative search method.

Built-in String, Integer and Double classes in Java implement Comparable interface so search method accepts these parameters.

package basics;

import java.util.Arrays;

public class GenericIterativeBinarySearch {

 public static <T extends Comparable<T>> boolean search( T[] items, T item ) {

  if (item == null) {
   return false;
  }

  int low = 0;
  int high = items.length - 1;

  while (low <= high) {

   int ix = low + (high - low) / 2;

   if (item.compareTo(items[ix]) < 0) {
    high = ix - 1;
   } else if (item.compareTo(items[ix]) > 0) {
    low = ix + 1;
   } else {
    return true;
   }
  }

  return false;
 }


 public static void main(String[] args) {

  Integer[] items = { 22, 55, 66, 11, 32, 56, 67, 89, 95, 10 };

  Arrays.sort(items);

  boolean found = search(items, Integer.valueOf(22) );
  System.out.println("Integer Array Contains item 22 = "+found);

  found = search(items, Integer.valueOf(11) );
  System.out.println("Integer Array Contains item 11 = "+found);

  found = search(items, Integer.valueOf(67) );
  System.out.println("Integer Array Contains item 67 = "+found);

  found = search(items, Integer.valueOf(10) );
  System.out.println("Integer Array Contains item 10 = "+found);

  found = search(items, Integer.valueOf(101) );
  System.out.println("Integer Array Contains item 101 = "+found);  
  
  found = search(items, null );
  System.out.println("Integer Array Contains item null = "+found); 
  
  String[] strItems = { "alk", "abc", "adk", "zyt", "fre", "nhy" };
  Arrays.sort(strItems);
  
  found = search( strItems, "alk" );
  System.out.println("String Array Contains item alk = "+found);
  
  found = search( strItems, "nhy" );
  System.out.println("String Array Contains item nhy = "+found);
  
  found = search( strItems, "zyt" );
  System.out.println("String Array Contains item zyt = "+found);
  
  found = search( strItems, "zyts" );
  System.out.println("String Array Contains item zyts = "+found);
  
  found = search( strItems, "null" );
  System.out.println("String Array Contains item null = "+found);
  
  Double[] dItems = { 11.3, 13.3, 6.0, 9.6, 45.7, 23.2 };
  Arrays.sort(dItems);
  
  found = search( dItems, 13.3 );
  System.out.println("Double Array Contains item 13.3 = "+found);
  
  found = search( dItems, 14.3 );
  System.out.println("Double Array Contains item 14.3 = "+found);
  
  found = search( dItems, 23.0 );
  System.out.println("Double Array Contains item 23.0 = "+found);  
  
 }
}

Create a GenericIterativeBinarySearch.java file in your workspace.

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

Integer Array Contains item 22 = true
Integer Array Contains item 11 = true
Integer Array Contains item 67 = true
Integer Array Contains item 10 = true
Integer Array Contains item 101 = false
Integer Array Contains item null = false
String Array Contains item alk = true
String Array Contains item nhy = true
String Array Contains item zyt = true
String Array Contains item zyts = false
String Array Contains item null = false
Double Array Contains item 13.3 = true
Double Array Contains item 14.3 = false
Double Array Contains item 23.0 = false

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

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

Binary Search Sorted Int Array Recursively

There exists a recursive solution for the binary search algorithm. At each step lower and higher bounds for the search interval are updated and the search key is scanned in this new updated interval.
For recursive binary search implementation; search interval is updated depending on the midPoint value.

midPoint = lowerBound+(higherBound-lowerBound)/2

For the starting step; lowerBound is 0 and higherBound is the last array index.

Following sample project created by qt creator and contains following files:
1- SearchIntArrayRecursively.pro
2- main.cpp

SearchIntArrayRecursively.pro file contains project configuration.

TEMPLATE = app
CONFIG += console
CONFIG -= app_bundle
CONFIG -= qt
SOURCES += main.cpp

main.cpp file contains main method and recursive binarySearch function implementations.

#include <stdio.h>

int getIndexOfItemRecursively(int pSearchedItem, int* pArray, int mLowerBound, int mHigherBound)
{
    if( mLowerBound > mHigherBound )
        return -1;
    int midIndex = mLowerBound+(mHigherBound-mLowerBound)/2;

    if( pSearchedItem < pArray[midIndex] )
        return getIndexOfItemRecursively(pSearchedItem, pArray, mLowerBound, midIndex-1);
    else if(pSearchedItem>pArray[midIndex])
        return getIndexOfItemRecursively(pSearchedItem, pArray, midIndex+1, mHigherBound );
    else
        return midIndex;
}

int findIndexOfItem( int pSearchedItem, int* pArray, int pTotalItemCount )
{
    return getIndexOfItemRecursively(pSearchedItem, pArray, 0, pTotalItemCount-1);
}

int main(int argc, char* argv[])
{
    int mArray[] = {1, 2, 4, 12, 34, 45, 56, 67, 78, 89, 90};
    int mLengthOfArray = sizeof(mArray)/sizeof(int);
    printf("There are %d items in the array\n", mLengthOfArray);
    printf("Items :\n");
    for(int i = 0; i<mLengthOfArray; i++)
    {
        if( i!=mLengthOfArray-1 )
            printf("%d,", mArray[i]);
        else
            printf("%d\n", mArray[i]);
    }
    printf("Indexes :\n");
    for(int i = 0; i<mLengthOfArray; i++)
    {
        if( i!=mLengthOfArray-1 )
            printf("%d,", i);
        else
            printf("%d\n\n", i);
    }
    int mSearchItem = 12;
    int mIndex = findIndexOfItem( mSearchItem, mArray, mLengthOfArray );
    if( mIndex!=-1 )
        printf("Item %d is at index %d\n", mSearchItem, mIndex);
    else
        printf("Item %d not found in the array\n",mSearchItem);

    mSearchItem = 89;
    mIndex = findIndexOfItem( mSearchItem, mArray, mLengthOfArray );
    if( mIndex!=-1 )
        printf("Item %d is at index %d\n", mSearchItem, mIndex);
    else
        printf("Item %d not found in the array\n",mSearchItem);

    mSearchItem = 91;
    mIndex = findIndexOfItem( mSearchItem, mArray, mLengthOfArray );
    if( mIndex!=-1 )
        printf("Item %d is at index %d\n", mSearchItem, mIndex);
    else
        printf("Item %d not found in the array\n",mSearchItem);

    return 0;
}

We can analyze the steps for the first search item 12.

Search for 12 :

• Find midPoint. For this case midPoint is at index 5. If the searchItem (12) is less than the item at index midPoint (45) then update higherBound value with midpoint-1.
• Search in the new range with new higherBound value. higherBound is now midPoint-1. And lowerBound is 0.

New Sub Array Shrinks To 5 Items:

• Find midPoint. For this case midPoint is at index 2. If the searchItem is higher than the item at index midPoint then update lowerBound value with midpoint+1.
• Search in the new range with new lowerBound value. lowerBound is now midpoint+1 and higherBound does not change for this case.

New Sub Array Shrinks To 2 Items :

• Find midPoint. For this case midPoint is at index 3.
• SearchedItem is not less than the item at midPoint.
• SearchedItem is not higher than the item at midPoint.
• Then item is at midPoint. Return index of midPoint.

When you run the above recursive binary search sample following console output is generated :

Binary Search Sorted Int Array Iteratively

Binary Search is one of the most widely known search algorithms. One of the main restrictions to use binary search for existing sets is that your list or container must be sorted before searching inside it.
Instead of searching a list or container by using linear-search algorithm, item-by-item, binary search is considered more efficient in terms of time and space.

Following sample project created by qt creator and contains following files:
1- SearchIntArray.pro
2- main.cpp

SearchIntArray.pro file contains project configuration.

CONFIG += console
TEMPLATE = app
SOURCES += main.cpp

main.cpp file contains main method and indexOfItem function implementations.

#include <stdio.h>

int indexOfItem(int pSearchedtem,int* pArray,int pTotalItemCount)
{
    int mLowerBound = 0;
    int mHigherBound = pTotalItemCount-1;

    while( mLowerBound<= mHigherBound )
    {
        int midIndex = mLowerBound+(mHigherBound-mLowerBound)/2;
        if( pSearchedtem < pArray[midIndex] )
            mHigherBound = midIndex-1;
        else if(pSearchedtem>pArray[midIndex])
            mLowerBound = midIndex+1;
        else
            return midIndex;
    }

    return -1;
}

int main(int argc, char* argv[])
{
    int mArray[] = {1, 2, 4, 12, 34, 45, 56, 67, 78, 89, 90};
    int mLengthOfArray = sizeof(mArray)/sizeof(int);
    printf("There are %d items in the array\n", mLengthOfArray);
    printf("Items :\n");
    for(int i = 0; i<mLengthOfArray; i++)
    {
        if( i!=mLengthOfArray-1 )
            printf("%d,", mArray[i]);
        else
            printf("%d\n", mArray[i]);
    }
    printf("Indexes :\n");
    for(int i = 0; i<mLengthOfArray; i++)
    {
        if( i!=mLengthOfArray-1 )
            printf("%d,", i);
        else
            printf("%d\n\n", i);
    }
    int mSearchItem = 12;
    int mIndex = indexOfItem(mSearchItem,mArray,mLengthOfArray);
    if( mIndex!=-1 )
        printf("Item %d is at index %d\n", mSearchItem, mIndex);
    else
        printf("Item %d not found in the array\n",mSearchItem);

    mSearchItem = 89;
    mIndex = indexOfItem(mSearchItem,mArray,mLengthOfArray);
    if( mIndex!=-1 )
        printf("Item %d is at index %d\n", mSearchItem, mIndex);
    else
        printf("Item %d not found in the array\n",mSearchItem);

    mSearchItem = 91;
    mIndex = indexOfItem(mSearchItem,mArray,mLengthOfArray);
    if( mIndex!=-1 )
        printf("Item %d is at index %d\n", mSearchItem, mIndex);
    else
        printf("Item %d not found in the array\n",mSearchItem);

    return 0;
}

indexOfItem function implements binary search algorithm in C programming language iteratively. indexOfItem function takes the item to search for inside the array as one of its incoming parameters and function returns the index of the found item or -1 if not was found.

Binary Search algorithm, as described at http://algs4.cs.princeton.edu/home/ ,
         
             - lowerBound = 0
             - higherBound = itemCount-1
             - loop until lowerBound is less than or equal to the upper bound
                       - divides the sorted container into 2 parts at the center, find middle index
                       - compares the searchKey with the the item which is at the middle index
                               - if the searchKey is greater than the item which is at the middle index
                                                     - then update the lower bound for search with (middle index+1)
                               - else if the searchKey is lower than the item which is at the middle index
                                                     - then update the upper bound for search with (middle index-1)
                               - else
                                       - then the searchKey is the item which is at the middle index
            - end loop
            return indexNotFound

main function contains 3 test-cases for binary search algorithm. First 2 searchKeys (12 and 89) are found in the test array whereas the last searchKey (91) is not found in the list.

Console output contains all the printf function results as follows :