Do you think IIT Guwahati certified course can help you in your career?
Introduction
Hello, Ninja! Do you want to learn Binary search in C using recursion? Then you are at the right place, as coding ninjas curated this article for you. In this article, we will explain Binary search in C using recursion. We will also consider an iterative approach for the same.
To understand the Binary search in C using Recursion, we will first try to understand recursion.
What is Recursion?
It is the process of a function calling itself, either directly or indirectly. The associated function is known as the recursive function. By using recursion, we can divide the given problem into smaller sub-problems similar to the given problem. The solution to these sub-problems is used to get the answer to the original problem.
You need to keep some points about recursion in mind before implementing it in your program. To avoid errors and confusion, remember these properties of recursion:
Recursion is used to perform the same operation with different inputs multiple times.
We attempt smaller inputs at each step to reduce the problem.
We need a base condition to stop the recursion at a certain point. Without a base condition, you will encounter infinite recursion. That's why the base condition is essential.
Every problem that can be solved using the recursive approach can also be solved using the iterative method.
Look at the following illustration to understand recursion better.
Now that we are familiar with recursion, let us understand Binary search.
The Binary search is one of the most efficient search algorithms. It is used to find an element (say "key") in a sorted list of elements. It utilizes the divide-and-conquer algorithmic pattern to search for the key element. It can be applied to any container as long as the elements are sorted and we know their indices.
Binary search compares the collection's middle element with the key. If the match is found (i.e., middle element = key), it returns the index of that element. If the key is smaller than the middle element, it is searched in the sub-potion to the left of the middle element. Otherwise, it looks for the key in the portion to the right of the middle item. Binary search is applied recursively on the sub-portion until its size reduces to zero.
Now let us see how Binary search works. We will consider the working of Binary search on an array.
How Binary Search Works
The following are some important points related to Binary Search:-
The given array must be in sorted order.
Initialize a variable left as 0 and right as the last index (size of the array - 1).
Calculate the mid index, then compare it with the target. If it is greater than the target, we will limit the search to the left half of the array. Otherwise, we will move to the right half. (the logic is reversed if the array is in decreasing order)
If the element at mid is equal to the target, the search is eliminated.
Now, we will discuss the algorithm in detail using an example.
Consider an array named “num” of size “9”. For the Binary search to work, we need to make sure that the given array is sorted. If the array is sorted we can move to further steps, but if it is not, our first step will be to sort the given array. Assume that following is the array we have to apply Binary search.
Since the array is unsorted, we will sort it first. After sorting, our array looks like this.
Now suppose we have to look for “14” in this array. We will use the Binary search for that. Firstly, we will find out the middle element of the array using the following formula:
middle = left + (right-left) / 2
Here, “left” is pointing to the first element of the array (index 0), and “right” is pointing to the last element of the array (index 8).
Let's see what happens when we plug these values into the formula.
So, we got 4 after putting these values in the given formula. Hence, the middle will now point to the fourth index.
Note: If you get a floating point value of “middle” after using this formula, use the integer part.
For example, if you get 3.5 as the middle value, use 3 (i.e., the integer value).
Look at the following image to visualize the positions of the left, right, and middle in our array.
Now we'll see if the value indicated by the middle is equal to the key.
Since the value of the key is less than the element pointed by the middle, we will look for the key in the left sub-array. The left sub-array will be between the current middle and the current left.
To search this subarray, we will make the following changes to the right and middle.
right = middle - 1
middle = left + (right-left) / 2
Here, “left” is pointing to the first element of the array (index 0), and “right” is pointing to the current middle -1 (index 3).
Let’s calculate the new value of the middle.
The new middle value turned out to be a floating-point number, 2.5. We will consider only the integer part of this number. Hence, the new middle will point at index 2.
Now let's look at the new positions of left, right, and middle in the following image
Now we'll see if the value indicated by the middle equals the key.
Since the element pointed by the middle is equal to the key, our search operation was successful. Hence, the key is found at index 2.
You must have noticed that the Binary search reduces the number of comparisons significantly.
Let us now understand the algorithm used to implement Binary search in C using recursion and iteration.
Assume that we have an array named “Num” of size “n,” and we have to find an element “key” in that array.
Step 1: START
Step 2: Initialize Left =0 and Right = n-1.
Step 3: Find the middle using the formula
Middle = Left + (Right - Left)/2.
Step 4: If Middle = key,
Then return “Middle” and print “element found.”
Step 5: If Middle > Key,
Then set Right = Middle-1 and GOTO step 3.
Step 6: If Middle < Key,
Then set Left = Middle + 1 and GOTO step 3.
Step 7: Repeat steps 3 to 6 till Left >= Right.
Step 8: If Left > Right
Return -1 and print “element not found.”
Step 9: STOP
Let us take a look at the flowchart of Binary search in C using recursion and iteration to understand the algorithm better.
Flowchart
The flowchart for Binary search in C is shown in the following image.
Iterative Approach
In the iterative Binary search approach, we will implement it using loops in C. We will loop over the same code block several times until the search operation is completed or all the elements have been checked.
Pseudo Code
Pseudo code for Binary search in C using an iterative approach is as follows:
// Pseudo code for Binary search
b_search(num, key, Left, Right)
repeat till Left >= Right
Middle = (Left + Right)/2
// If the key is present in the middle of the array.
if (num[Middle] == key)
return Middle
// If the key is less than the middle element.
else if (num[Middle]> Key)
Right = Middle - 1
// If the key is more than the middle element.
else
Left = Middle + 1
// Iterative implementation of Binary search
#include <stdio.h>
int b_search(int num[], int Left, int Right, int key) {
int Middle = 0;
while (Left <= Right) {
Middle = Left + (Right - Left) / 2;
// If the key is present in the middle of the array
if (num[Middle] == key){
return Middle;
}
// If the key is Smaller than the element in the middle check the left subarray.
if (num[Middle] > key){
Right = Middle - 1;
}
// If the key is greater than the element in the middle, check the right subarray.
else{
Left = Middle + 1;
}
}
// If the element is not found
return -1;
}
int main() {
int size = 0, key = 0, found = 0;
printf("Enter the size of the array: ");
scanf("%d", & size);
int num[size];
printf("Enter the elements of the array in ascending order: ");
for (int i = 0; i < size; i++) {
scanf("%d", & num[i]);
}
printf("Enter the element to be searched: ");
scanf("%d", & key);
found = b_search(num, 0, size - 1, key);
if (found == -1) {
printf("Element is not present in the array");
}
else {
printf("Element found at index %d", found);
}
return 0;
}
Enter the elements of the array in ascending order: 6 8 14 16 18 20 23 32
Enter the element to be searched: 14
Output
Complexities
Time Complexity
O(log n) is the time complexity. Here, n is the size of the array.
Reason: It is because the number of iterations required to find an element is log(n).
Space Complexity
O(1) is the space complexity.
Reason: It is because we are not using any extra space in the search operation.
Recursive Approach
To implement Binary search in C using recursion, we will call the binary search function recursively until either our search is completed or all the elements of the array are checked.
Pseudo Code
The Pseudo code for Binary search in C using recursion is as follows:
// Pseudo code for implementation of binary search using a recursive approach
b_search(num, key, Left, Right)
if Left > Right
return -1
else
Middle = (Left + Right) / 2
// If the key is equal to the middle element
if num[Middle] == key
return Middle
// If the key is greater than the middle element
else if key > arr[mid]
return b_search(num, key, Middle + 1, Right)
// If the key is less than the middle element
else
return b_search(num, key, Left, Middle - 1)
// Recursive implementation of Binary search
#include <stdio.h>
int b_search(int num[], int Left, int Right, int key) {
int Middle = 0;
while (Left <= Right) {
Middle = Left + (Right - Left) / 2;
// If the key is present at the middle of the array
if (num[Middle] == key){
return Middle;
}
// If the key is Smaller than the element at the middle check the left subarray.
if (num[Middle] > key){
return b_search(num, Left, Middle-1, key);
}
// If the key is greater than the element in the middle, check the right subarray.
else{
return b_search(num, Middle+1, Right, key);
}
}
// If the element is not found
return -1;
}
int main() {
int size = 0, key = 0, found = 0;
printf("Enter the size of the array: ");
scanf("%d", & size);
int num[size];
printf("Enter the elements of the array in ascending order: ");
for (int i = 0; i < size; i++) {
scanf("%d", & num[i]);
}
printf("Enter the element to be searched: ");
scanf("%d", & key);
found = b_search(num, 0, size - 1, key);
if (found == -1) {
printf("Element is not present in the array");
}
else {
printf("Element found at index %d", found);
}
return 0;
}
O(log n) is the time complexity. Here, n is the size of the array.
Reason: It is because the number of iterations required to find an element is log(n).
Space Complexity
O(log n) is the space complexity. Here, n is the size of the array.
Reason: It is because we are using extra space in the stack while making the recursive calls for the Binary search function. Since we are making log(n) calls in this implementation, the space complexity becomes O(log n)
Sorting involves putting information in a meaningful order. It allows us to evaluate the data more efficiently.
What principle is used in the Binary search algorithm?
Divide and conquer is the principle behind this search algorithm. The data should be in sorted form for this algorithm to function correctly.
Can Binary search be applied to a linked list?
If the list is ordered and you are aware of the number of elements in the list, the Binary search is possible on the linked list.
What are the drawbacks of Binary search?
It has a more complex code structure and uses more stack space than sequential search methods. Another disadvantage is that the data needs to be sorted for the Binary search to work.
What are the advantages of Binary search?
A sorted array of extensive data can be quickly and effectively searched for an element or key value using the binary search method.
Conclusion
We understood the binary search algorithm in detail. We also implemented the code for binary search in C using recursion and iteration.
85+ registered