Binary Search Algorithm In C

Data storage systems, information retrieval tools, and data manipulation are some of the key applications that implement the binary search algorithm.

Characteristics:

• ✅ The array of input values must be sorted.
• ✅ With each iteration, the method shrinks the search range by half, making it particularly efficient for huge datasets.
• ✅ The algorithm has an O (log n) worst-case time complexity.
• ✅ Finding the desired value is done by the programme using a divide-and-conquer strategy.

Here is a simple illustration of the binary search algorithm implemented in the C programming language:

#include <stdio.h>

int binary_search(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;  // Target not found
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 5;

    int index = binary_search(arr, 0, n - 1, target);

    if (index == -1) {
        printf("Target not found\n");
    } else {
        printf("Target found at index %d\n", index);
    }

    return 0;
}

Output:

Target found at index 2

• ✅ The binary_search function accepts four arguments: the array to search, the left and right search range boundaries, and the target value to look for. The function returns its index if the desired value can be found; else, it returns -1.
• ✅ The main function creates an array arr and a value target. The binary_search function is then used to search the array for the desired value. The function returns the index where the target value was located if it was, the function returns the index at which it was found. Otherwise, the message "Target not found" is displayed.
• ✅ The binary search algorithm's implementation is basic. We begin by setting the left border to the array's initial index and the right boundary to the array's last index. Once the left boundary is less than or equal to the right border, the array is looped through one more time. We use the formula (left + right) / 2 within the loop to calculate the middle index of the search range. This formula computes the integer value of the middle index's floor.
• ✅ The centre member of the array is contrasted with the target value. We return the index of the middle element if they are equal. We change the right boundary to be one less than the middle index if the desired value is less than the middle element. If not, we adjust the left border so that it is one more than the centre index. We continue doing this until the goal value is obtained or the search space is filled.
• ✅ The temporal complexity of the binary search algorithm, where n is the array size, is O(log n). This is far more efficient than linear search, which has a temporal complexity of O(n), where n is the size of the array.
• ✅ Finally, the binary search technique offers a useful way to locate a particular member in a sorted array. It is easy to build and has an O(log n) time complexity, making it an efficient approach for large datasets.

Advantages:

• ✅ For large datasets, the binary search algorithm is exceptionally efficient, and it is capable of handling a wide range of input sizes.
• ✅ The algorithm is simple to implement in almost all programming languages.

Disadvantages:

• ✅ Before using the binary search technique, the input array must be sorted, which takes more time and memory.
• ✅ The algorithm cannot be applied to unsorted arrays.
• ✅ The algorithm may yield inaccurate results if the input array is not sorted.
• ✅ The binary search algorithm is not appropriate for tiny datasets since the technique's overhead may outweigh its benefits.

Conclusion:

A sorted array enables swift retrieval of a particular element through the binary search method. This approach utilizes a divide-and-conquer tactic to halve the search scope iteratively, ensuring optimal performance especially with extensive datasets. Prior to implementing binary search, it is essential to arrange the input array in ascending order, a process that demands additional time and memory resources. The binary search algorithm stands out as a sophisticated computational technique extensively employed across diverse industries.