Binary Search in C Program

Searching is one of the most basic operations in programming languages. It is a process in which we locate a particular given element in the list of elements. If the element is located then it can return the index at which the element is present but if the element is not located then it will display “Element not found”.

In C programming language, Searching is of two types: one is Sequential or Linear Search and second is Binary Search.

What is Binary Search in C?

Binary Search is an efficient and powerful searching algorithm that is used to locate an element in a sorted array. It is a divide-and-conquer algorithm which locates a given element in a sorted array by dividing the search area i.e. the given array in half repeatedly.

NOTE: Given array must be sorted for getting optimal solution.

Binary Search Algorithm in C

Firstly, we compare the given element with the element at middle position in the array and then if the element is located then index value is returned, at which the element is present. Otherwise, the array is divided in two parts, if the element is greater than the element at middle index then the element is searched in the right subarray else it will search in left subarray. This process is repeated until the element is found or the subarray is unbreakable.

Example

1. Let the target=10.

2. Given array:

3. Set ‘low’ and ‘high’ index.

4. Calculate the mid index by using formula mid=low+(high-low)/2. Here, mid=2.

5. If arr[mid]==target, then return the mid. Else, check whether arr[mid]>target or not. If arr[mid]>target, then we will search on left subarray. Else, we will search in right subarray.

6. In this example, arr[mid]!=target. So, now we will divide the array into left and right subarrays. Here, arr[mid]>target, so we will search in left subarray.

7. Repeat step 4 and 5 until the target element is found or the subarray is indivisible. We will again calculate the mid.

Here, mid=0.

8. Again, arr[mid]!=target. So, we will again divide the array into left and right subarrays. Here, arr[mid]<target, so we will search in right subarray.

9. Repeat step 7. Here, mid=1.

10. Now, arr[mid]==target. Since, the target element is found, we will return the mid i.e. mid=1 is returned.

Approaches of Binary Search Program in C

Binary Search program in C is implemented by using two approaches:

1. Iterative Approach
2. Recursive Approach

Let’s explore them in detail.

Binary Search Program in C (Iterative Approach)

In this approach, we use while loop for repeatedly updating the search space until the given element is found or the subarray is unbreakable.

Algorithm

1. Take array and the target element as input.
2. Define a function named “iterativeBinarySearch”.
3. In “iterativeBinarySearch” function, use while loop to search the element in subarrays by comparing the mid values of the subarrays.
4. In “iterativeBinarySearch” function, if element is found it will return the index at which the element is found, otherwise, it will return -1.
5. In main() function, use if-else statement to display the found or not found message.

Source Code

#include <stdio.h>

int iterativeBinarySearch(int arr[], int target, int size) {
    int low = 0, high = size - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return mid;
        }
        else if (arr[mid] > target) {
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }

    return -1;
}

int main() {
    int size, target;

    printf("Enter the size of the array: ");
    scanf("%d", &size);

    int arr[size];

    printf("Enter the elements of the sorted array:\n");
    for (int i = 0; i < size; ++i) {
        scanf("%d", &arr[i]);
    }

    printf("Enter the target element to search: ");
    scanf("%d", &target);

    int result = iterativeBinarySearch(arr, target, size);

    if (result != -1) {
        printf("Element found at index %d.\n", result);
    } else {
        printf("Element not found in the array.\n");
    }

    return 0;
}

Output

Binary Search Program in C (Recursive Approach)

In this approach, break down the problem into subproblems by using recursion and by making recursive calls we search for the given element.

Algorithm

1. Take array and target element as input.
2. Define a function named “recursiveBinarySearch”.
3. In “recursiveBinarySearch” function, we will define a base condition first (i.e. low>high) and then we will use if-else statement to compare the middle element with target element.
4. This function will return -1 if the target element is not found and index value if the element is found.
5. In main() function, use if-else statement to display the found or not found message.

Source Code

#include <stdio.h>

int recursiveBinarySearch(int arr[], int target, int low, int high) {
    if (low > high) {
        return -1;
    }

    int mid = low + (high - low) / 2;

    if (arr[mid] == target) {
        return mid;
    }
    else if (arr[mid] > target) {
        return recursiveBinarySearch(arr, target, low, mid - 1);
    }
    else {
        return recursiveBinarySearch(arr, target, mid + 1, high);
    }
}

int main() {
    int size, target;

    printf("Enter the size of the array: ");
    scanf("%d", &size);

    int arr[size];

    printf("Enter the elements of the sorted array:\n");
    for (int i = 0; i < size; ++i) {
        scanf("%d", &arr[i]);
    }

    printf("Enter the target element to search: ");
    scanf("%d", &target);

    int result = recursiveBinarySearch(arr, target, 0, size - 1);

    if (result != -1) {
        printf("Element found at index %d.\n", result);
    } else {
        printf("Element not found in the array.\n");
    }

    return 0;
}

Output

Time Complexity:

Space Complexity:

In Iterative approach, Space Complexity is O(n), where n is the size of the array. In Recursive approach, the space complexity is O(log n) as it is determined by the maximum depth of the recursive call.

Advantages of Binary Search

1. Binary Search is faster and more efficient than Linear Search.
2. Binary Search is space efficient as the size of search space reduces with each iteration.
3. Binary Search works well with large-size arrays.
4. It is simple, efficient, and versatile searching algorithm.

Disadvantages of Binary Search

1. Binary Search only works for sorted arrays.
2. Binary Search requires extra memory in case of recursive approach.
3. Binary Search is not efficient for small-sized arrays.
4. It is not suitable for dynamic datasets having frequent updates.

Conclusion

Binary Search Algorithm in C is a crucial algorithm for solving searching problems optimally. It works well with large arrays and thus, it is useful for solving complex problems. By understanding this algorithm, you can enhance the performance of the programs. As we will move further in our programming journey, these concepts will help us in understanding of more complex concepts. Happy Learning!

Goto Statements In C

Strong Number In C

I hope You liked the post 👍. For more such posts, 📫 subscribe to our newsletter. Try out our free resume checker service where our Industry Experts will help you by providing resume score based on the key criteria that recruiters and hiring managers are looking for.

FAQ