Binary Search using Recursion in Java

In this tutorial, I am going to discuss the implementation of a Binary search using recursion in java.

Given an array of sorted integers and a number k. We have to write a code to search  an element k in an array.

For example:

Input: {2, 3, 4, 5, 7, 8},     k = 5

Output: 3 (5 is found at 3rd index)

Input array is sorted and we have to find 5 in this array. The element is found at index 3.

We can search an element in array either by using Linear search or Binary search.

When an array is sorted then definitely searching an element through Binary search will take O(logn) time complexity as compared to linear search which take O(n) time complexity.

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

Difference between recursion and iteration

In this tutorial, I am going to discuss it’s recursive implementation.

Binary Search using Recursion in Java

Binary Search using Recursion in Java

How Does Binary Search Algorithm Works?

i) Binary search algorithm works only for sorted array.

ii) In Binary search, first we compute mid by using start and end index. Then we compare the value present at mid index to the value k. 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(logn).

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

b) Worst case – The 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 algorithm explained with example

Binary Search algorithm explained with example

Programming video tutorials

Programming questions on Binary Search

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.

Binary Search Algorithm Implementation using Recursion – Video Tutorial

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

Tagged , . Bookmark the permalink.

About WebRewrite

I am technology lover who loves to keep updated with latest technology. My interest field is Web Development.