Java program for Binary Search Using Recursion

Java | Binary search using recursion: Here, we are implementing a java program for binary search using recursion.
Submitted by Indrajeet Das, on December 13, 2018

Given an integer sorted array (sorted in increasing order) and an element x, find the x in given array using binary search. Return the index of x. Return -1 if x is not present in the given array.

Input format:

    Line 1: Array size
    Line 2: Array elements (separated by space)
    Line 3: x (element to be searched)

Sample Input:

    6
    2 3 4 5 6 8 
    5

Explanation:

To solve binary search using recursion, instead of using a while loop we call the recursive function at the end with respective parameters. We keep a start, end int parameters to get the range of the array. We find mid using start and end and if the element at mid is greater than the element to be found, we put end = (mid -1) or else start = (mid +1). If it is same, we return mid. If no element is found we return -1.

Example:

    Let the Array be 1 2 3. Start = 0, end = 2
    We find for number 1.
    
    First Traversal:  mid = (0+2)/2 = 1
    Since 2>1 , end = 1-1 = 0
    
    Second Traversal:
    Mid = 0
    And hence, 0 will be returned.

Algorithm:

Declare a recursive function towerOfHanoi with parameters (int disk, char source, char auxiliary, char destination)

Step 1: Declare a recursive function with parameters (int arr[], int ele, int start, int end)
Step 2: Base Case : if(start> end) return -1.
Step 3: Let int mid = (start + end)/2;
Step 4: if(arr[mid] == ele) return mid;
Step 5: if(arr[mid] >ele) end = mid -1;
Else start = mid +1;
Step 6: Return Recursive func(arr,ele,start,end);

Program:

import java.util.Scanner;

public class Main {
  // Recursive Function
  public static int binarySearch(int input[], int element) {
    // Write your code here
    int start, end;
    start = 0;
    end = input.length - 1;
    //Call to helper function
    return binarySearch(input, element, start, end);
  }

  //Helper Function
  public static int binarySearch(int input[], int element, int start, int end) {
    //Base Case
    if (start >= end) {
      if (input[end] == element) {
        return end;
      } else {
        return -1;
      }
    }

    //Comparisions
    int mid = (start + end) / 2;
    if (input[mid] == element) {
      return mid;
    } else if (input[mid] > element) {
      //Recursive Call
      return binarySearch(input, element, start, mid - 1);
    } else {
      //Recursive Call
      return binarySearch(input, element, mid + 1, end);
    }
  }

  //Main
  public static void main(String[] args) {
    int arr[] = new int[10];

    System.out.println("Enter 10 integers in ascending order.");
    Scanner s = new Scanner(System.in);

    for (int i = 0; i < 10; i++) {
      arr[i] = s.nextInt();
    }

    System.out.println("Enter the number you want to search.");
    int num = s.nextInt();

    int res = binarySearch(arr, num);

    if (res != -1) {
      System.out.println("The number is at index: " + res);
    } else {
      System.out.println("Number Not Found.");
    }
  }
}

Output

First run:
Enter 10 integers in ascending order.
2 4 6 8 10 12 14 16 18 20
Enter the number you want to search.
2
The number is at index: 0   

Second run:
Enter 10 integers in ascending order.
2 4 6 8 10 12 14 16 18 20
Enter the number you want to search.
18
The number is at index: 8   

Third run:
Enter 10 integers in ascending order.
2 4 6 8 10 12 14 16 18 20
Enter the number you want to search.
3
Number Not Found.