Write C and Java programs to implement recursive binary search on a sorted array.

Here, we develop C and Java code to implement binary search using recursion. We develop a method recBinarySearch that takes a sorted array arr storing n integers, where n >= 1 and the search key, and returns the location of the search key if found; else -1.

Binary search looks at the middle element of the list and see if the element sought-for is found. If not, than it compares the sought-for element with the middle element of the array and check whether the middle element is larger than the element we are trying to find. If so, we keep looking in the first half of the list; otherwise, we look in the second half. It cuts the number of elements to be compared by half. We keep going in the same way until the item is found or it is determined that the sought-for element is not present in the list.

Following are the Java and C codes respectively to implement binary search using recursion.

C program for recursive binary search

#include <stdio.h>
 
int recBinarySearch(int*, int, int, int);
 
int main()
 {
    int arr[] = {11, 12, 13, 14, 15, 16, 17, 18 ,19, 20};
    int key = 13;
    int found = recBinarySearch(arr, key, 0, 10);
 
    if (found > -1)
    {
      printf ("%d found on location: %d\n", key, found);
    }
    else
    {
      printf("Item not found.\n");
    }
 }
 
int recBinarySearch(int arr[], int key, int low, int high)
{
  int mid;
  if (high < low)
  {
    return -1;
  }
 
  mid = (low + high) / 2; 
 
  if (arr[mid] < key)
    return recBinarySearch(arr, key, mid + 1, high);
  else if (arr[mid] > key)
    return recBinarySearch(arr, key, low, mid - 1);
  else
    return mid;
}
 
OUTPUT
======
13 found on location: 2

Java program for recursive binary search

class RecursiveBinarySearch
{
  public static void main (String[] args)
  {
    int arr[] = {11, 12, 13, 14, 15, 16, 17, 18 ,19, 20};
    int found = recBinarySearch(arr, 13, 0, arr.length - 1);
 
    if (found > -1)
    {
      System.out.println ("Item found on location: " + found);
    }
    else
    {
      System.out.println("Item not found");
    }
  }
 
  static int recBinarySearch(int[] arr, int key, int low, int high)
  {
    int mid;
    if (high < low)
    {
      return -1;
    }
 
    mid = (low + high) / 2; 
 
    if (arr[mid] < key)
      return recBinarySearch(arr, key, mid + 1, high);
    else if (arr[mid] > key)
      return recBinarySearch(arr, key, low, mid - 1);
    else
      return mid;
  }  
}
OUTPUT
======
D:\JavaPrograms>javac RecursiveBinarySearch.java
 
D:\JavaPrograms>java RecursiveBinarySearch
Item found on location: 2

Hope you have enjoyed reading C and Java programs for recursive binary search. Please do write us if you have any suggestion/comment or come across any error on this page. Thanks for reading!



Get Free Tutorials by Email

About the Author

is the main author for cs-fundamentals.com. He is a software professional (post graduated from BITS-Pilani) and loves writing technical articles on programming and data structures.

Today's Tech News

Plans drawn up for world's tallest wooden skyscraperPosted on Monday February 19, 2018

The 70-storey tower would be 90% wood and have trees and other foliage on every level.

Probe after 'drone made helicopter crash'Posted on Monday February 19, 2018

Investigations are launched after a helicopter reportedly crashed after swerving to avoid a consumer drone.

Dark web paedophile Matthew Falder jailed for 32 yearsPosted on Monday February 19, 2018

Matthew Falder blackmailed victims into sending sexual images that he then shared on the dark web.

Courtesy BBC News

AD BLOCKER DETECTED!

Advertisements help running this site for free.


To view the content please disable AdBlocker and refresh the page.

×