Write a program to implement a Binary search using recursion in java. In this tutorial, I am going to discuss binary search algorithm and it’s implementation using recursion in Java.

In my previous tutorial, i have explained how to implement binary search in java using iterative approach.

Difference between recursion and iteration

## How Does Binary Search Algorithm Works?

i) Binary search algorithm works only for **sorted array**.

ii) In binary search, we start by comparing middle element of the array with the search value. If search value is found, then the index of the middle element is returned. If the search value is less than or greater than the middle element, than the search continues in the lower or upper half of the array.

iii) The time complexity of binary search is O(n).

a) **Best case** time complexity of binary search is O(1) (when element in found at mid index)

b) **Worst case** time complexity of binary search is O(logn)

Find first and last position of a number in a sorted array

In this example, i have explained how binary search works.

## Binary Search using Recursion in Java

I have explained what is binary search? And how it works. Let’s write a java code to implement binary search using recursion.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | /** * Binary Search implementation in java using recursion */ public class BinarySearch { public static void findRecursively(int arr[], int start, int end, int search) { if(start > end) { return; } int mid = (start + end)/2; if(arr[mid] == search) { System.out.println(mid); return; } else if(search > arr[mid]) { findRecursively(arr, mid+1, end, search); } else { findRecursively(arr, start, mid - 1, search); } } public static void main(String[] args) { int arr[] = {10, 12, 14, 15, 16, 20}; int search = 16; int start = 0; int end = arr.length-1; findRecursively(arr, start, end, search); } } |

## Binary Search using Recursion Video Tutorial

In this video tutorial, I have explained step by step how we can implement binary search using recursion in java.