Binary search with recursion

Introduction to Binary search with recursion

Binary search is a searching algorithm, in which finds the location of the target value in an array. It is also called a half interval search or logarithmic search. In the searching algorithm, we search any element in the array and return the position of an element in the array. The basic search algorithm is Linear Search, in which we compare every element in an array linearly with the target element. In the Binary Search algorithm, we take a sorted array and compare it with the middle of the array. If we don’t find the target element, we divide it by middle and search in half array accordingly until we get the target element. The time complexity of the Binary Search algorithm is O (log N). where as in linear search, it was O(N), where is N is the size of the array. The base of the log is always 2. In this topic, we are going to learn about Binary search with recursion.

How to perform binary search tree insertion?

To perform a binary search, it is a condition that the array should be sorted; in a sorted array, we compare the middle value of the array with the target value.

If the middle value is greater than the target value, then it means that the target value is the left side of the middle value because the array is sorted so we find the target value in the left half of the array and again compare it with the middle of the left half array.

If the middle value is smaller than the target value, then it means that the target value is the right side of the middle value because an array is sorted, so we find the target value in the right half of the array and again compare it with the middle of the right array.

If the middle value is equal to the target value, then we simply return the middle.

For binary search, create function we take an array, starting index, ending index of the array and target value. Initial pass the 0 as starting index and N-1 as ending index where N is the size of the array. In binary search, first, we get the middle index of the array using this equation: –

Middle = starting index + (ending index – starting index) / 2

After getting middle, we compare the target value with the value at the middle index; if the value at the middle index is greater, we call the binary search function recursively and pass the same starting index and update the ending index with middle-1. If the value at the middle index is smaller, then we call the binary search function recursively and pass the starting index as middle+1, and the ending index will be the same.

If, in any case ending index is less than starting index, that means the target value is not present in the array, so we will return -1 in that case.

Examples of Binary search with recursion

To understand completely binary search, we will take two examples: –

1. When the target value is in the Array. Let’s take this below array, and the target value is 9.

Step 1. Call the function binarySearch and pass the required parameter in which the target value is 9, starting index and ending index of the array is 0 and 8.

Step 2. As we see that the starting index is lesser than the ending index, we find the middle using this equation. Middle = starting index + (ending index – starting index) / 2.

Middle = 0 (8-0)/2 = 4

Step 3. Compare the Target value with arr[4]. arr[4] is 21, which is greater than the target value, so we call the recursively binarySearch function and pass the starting index the same, but the ending index will be the middle -1.

Step 4. As the starting index is 0 and the ending index is 3, the middle index will be 1.

Step 5. Compare the Target value with arr[1]. Arr[1] is 5, which is smaller than the target value, so we call recursively binarySearch function and the pass the starting index middle +1 because here arr[middle] is smaller and the ending index will be the same.

Step 6. As the starting index is 2 and the ending index is 3, the middle index will be 2.

Step 7. Compare the Target value with arr[2]. Arr[2] is 9, now target value and arr[middle] is same. So now, we simply return to the middle.

So this is how we will get the index of the target value. And then print the position of the target value.

2. When the target value is not in the array, Let’s take 11 as a target value which is not present in the array.

Step 1. Call the function binarySearch and pass the required parameter in which target value is 11, starting index and ending index of an array is 0 and 8.

Step 2. As we see that the starting index is lesser than the ending index, we find the middle using this equation. Middle = starting index + (ending index – starting index) / 2.

Middle = 0 (8-0)/2 = 4

Step 3. Compare the Target value with arr[4]. arr[4] is 21, which is greater than the target value, so we call recursively binarySearch function and the pass the starting index same but ending index will the middle -1.

Step 4. As the starting index is 0 and the ending index is 3, the middle index will be 1.

Step 5. Compare the Target value with arr[1]. Arr[1] is 5, which is smaller than the target value, so we call the recursively binarySearch function and the pass the starting index middle +1 because here arr[middle] is smaller and the ending index will be the same.

Step 6. As the starting index is 2 and the ending index is 3, the middle index will be 2.

Step 7. Compare the Target value with arr[2]. Arr[2] is 9, now target value is greater than arr[middle]. So we again call recursively binarySearch and pass the starting index middle +1, which is 3, and the ending index will be the same as 3.

Step 8. Here ending index is not less than starting index, so we find the middle of starting index and ending index. The middle will be 3, arr[3] is 13, which is greater than the target value. So we again call recursively binarySearch and pass the starting index as same and ending index as middle -1, which is 2.

Step 9. Here we get that starting index is 3 and the ending index is 2, which is lesser, So we will return -1, which means the target value is not in the array.

Implementation:

When the target value is present

#include<bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int target, int start, int end) {
if( end >= start) {
int middle = start + (end - start)/2;
if( arr[middle] == target ) {
return middle;
}
if( arr[middle] > target ) {
return binarySearch(arr, target, start, middle-1);
}
return binarySearch(arr, target, middle+1, end);
}
return -1;
}
int main() {
int arr[] = { 2, 5, 9, 13, 21, 39, 50, 55, 60 };
int N = sizeof(arr)/sizeof(arr[0]);
int res = binarySearch(arr, 9, 0, N-1 );
if(res == -1) {
cout << "Target value Not Found" << endl;
}
else {
cout << "Position of target value is " << res+1 << endl;
}
}

Output:-

Implementation:-

When the target value is not present

#include<bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int target, int start, int end) {
if( end >= start) {
int middle = start + (end - start)/2;
if( arr[middle] == target ) {
return middle;
}
if( arr[middle] > target ) {
return binarySearch(arr, target, start, middle-1);
}
return binarySearch(arr, target, middle+1, end);
}
return -1;
}
int main() {
int arr[] = { 2, 5, 9, 13, 18, 31, 39, 50, 55, 60 };
int N = sizeof(arr)/sizeof(arr[0]);
int res = binarySearch(arr, 11, 0, N-1 );
if(res == -1) {
cout << "Target value Not Found" << endl;
}
else {
cout << "Position of target value is " << res+1 << endl;
}
}

Output:-

Conclusion

Binary Search required a sorter array, but here time complexity is better than linear searching. Similar to binary search, there is another algorithm called Ternary Search, in which the first array is in increasing order than decreasing order.

Recommended Articles

This is a guide to Binary search with recursion. Here we discuss How to perform binary search tree insertion along with the examples and outputs. You may also have a look at the following articles to learn more –

1. Binary Search C++
2. BinaryWriter in C#
3. C# BinaryReader
4. Binary Search Tree Types