Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Recursion?
3.
Binary Search
4.
How Binary Search Works
5.
Binary Search Algorithm
6.
Flowchart
7.
Iterative Approach
7.1.
Pseudo Code
7.2.
Implementation in C
7.2.1.
Input 
7.2.2.
Output
8.
Complexities
8.1.
Time Complexity
8.2.
Space Complexity
9.
Recursive Approach
9.1.
Pseudo Code
9.2.
Implementation in C
9.2.1.
Input 
9.2.2.
Output
10.
Complexities
10.1.
Time Complexity
10.2.
Space Complexity
11.
Frequently Asked Questions
11.1.
What is Sorting?
11.2.
What principle is used in the Binary search algorithm?
11.3.
Can Binary search be applied to a linked list?
11.4.
What are the drawbacks of Binary search?
11.5.
What are the advantages of Binary search?
12.
Conclusion
Last Updated: Mar 27, 2024
Easy

Binary Search in C Using Recursion

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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. 

binary search in c using recursion

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.

illustration of recursion

Now that we are familiar with recursion, let us understand Binary search.

Click on the following link to read further: Features of C Language and  Tribonacci Series.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 is the optimal searching algorithm

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. 

example array

Since the array is unsorted, we will sort it first. After sorting, our array looks like this.

array after sort

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.

positions of left, right and middle

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.

searching in left subarray

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

new positions of left, right and middle

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.


You can also read about dynamic array in c

Binary Search Algorithm

The algorithm for Binary search is as follows:

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.

flowchart

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

Implementation in C


// 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;
}

Input 

Enter the size of the array: 8

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

output of iterative code

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) 

Implementation in C

// 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;
}

 

Input 

Enter the size of the array: 6

Enter the elements of the array in ascending order: 3 6 7 10 12 14

Enter the element to be searched: 10

Output

output of recursive approach


You can practice by yourself with the help of online c compiler.

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(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) 

Must Read Recursion in Data Structure

Frequently Asked Questions

What is Sorting?

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.

We hope this article helps you on your journey. You can solve some problems, like writing a program for printing the table of any number or a C program to find if a number is odd or even.

You can refer to these articles related to DSA by Coding Ninjas.

Recommended problems -

 

You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingSystem Design, and many more!

Head to our practice platform, Coding Ninjas Studio, to practice top problems, attempt mock tests, read interview experiences and interview bundles, follow guided paths for placement preparations, and much more!

Happy coding, Ninja!

Previous article
How to Convert Binary to Hexadecimal?
Next article
Star Patterns Program in C
Live masterclass