Programming Tutorials and Interview Questions

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!

The BBCâ€™s technology correspondent Rory Cellan-Jones gets a beer poured for him by a robotic barman - but how long does it take?

US politicians have voted to let ISPs gather and sell data about what Americans do online.

Customers who suffer poor service could get automatic payouts under Ofcom's plan.