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