Write a program to implement binary search using recursion in c.
Given a sorted array, write a code to search an element in an array.
For example –
Example1 : arr[] = {1, 3, 5, 6, 7} target = 5
The element 5 is found at index 2.
We have given a sorted array, we can use binary search algorithm to search an element efficiently.
Binary Search
Binary Search is a searching algorithm that search an element in a sorted array in O(logN) time complexity.
In binary search, we first calculate the mid. In next step, we compare element present at mid index to the target value. If target value is found, we return the mid index. Else If the search value is less than or greater than the middle element, the search continues in the lower or upper half of the array.
Important Points
i) A Binary search algorithm is applicable only for sorted values. An array should be sorted either in ascending or descending order.
ii) The time complexity of binary search is O(log(n)).
In my previous post, I have discussed Binary search program in c using iterative approach. In this post, I am going to explain how to implement a binary search program in c using recursion.
What is Recursion?
Recursion is a programming technique in which function call itself until the base condition is reached.
In my previous tutorials, i have explained what is Recursion and what’s the Difference Between Recursion and Iteration.
Binary Search using Recursion in C
How to Implement Binary Search Algorithm using Recursion
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
BinarySearch (int arr[], int num, int first, int last) { if (first > last) { print value not found; } else { /* Calculate mid element */ int mid = (first + last) / 2 ; if(arr[mid]==num) { print number_is_found; } if (arr[mid] > num) { /* key is in lower subset of array */ //recursive call BinarySearch (arr, num, first, mid-1); } else if (arr[mid] < num) { /* Key is in higher subset */ //recursive call BinarySearch (arr, num, mid +1 , last); } } |
Binary Search using Recursion in C
We have discussed what is binary search algorithm and how to implement them recursively. Let’s write a c code which implement binary search algorithm 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
/* * Binary Search Algorithm using Recursion */ #include <stdio.h> #include <stdlib.h> void BinarySearch(int arr[], int num, int first, int last){ if(first > last){ printf("Number is not found"); } else { int mid; //calculate mid mid = (first + last)/2; //if value is found at mid position if(arr[mid]==num){ printf("Element is found at index %d ",mid); exit(0); }else if(arr[mid]>num){ //Recursive call BinarySearch(arr, num, first, mid-1); }else{ //Recursive call BinarySearch(arr, num, mid+1, last); } } } main() { int arr[] = {2,5,7,9,12,15,18}; //Search 9 in a sorted array int num = 9; int first =0 , last = (sizeof(arr)/sizeof(arr[0]))-1; BinarySearch(arr, num, first, last); } |
Binary Search using Recursion in Java
Binary Search Algorithm Explained in Hindi – Video Tutorial
In this video tutorial, I have explained binary search algorithm using example.
Binary search algorithm explained video tutorial
Binary search program in java video tutorial
Books For Algorithm
For data structure you can refer these books.
Data Structure Books on Amazon
