# 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) {
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;

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 {
}
}
}
```

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
```

Top MCQs

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates