Binary search algorithm

Binary search is a searching algorithm that is used to find the position of a target value within a sorted array or list. It works by repeatedly dividing the search space in half until the target value is found or it is determined that the value does not exist in the array.

The algorithm compares the target value with the middle element of the array. If they are equal, the search is successful and the index of the middle element is returned. If the target value is less than the middle element, the search continues on the lower half of the array. If the target value is greater than the middle element, the search continues on the upper half of the array.

By dividing the search space in half at each step, binary search efficiently reduces the number of elements that need to be examined, leading to a significant improvement in search time compared to linear search algorithms. Binary search is particularly efficient for large sorted arrays.

It is important to note that binary search requires the array to be sorted in order to work correctly. If the array is not sorted, the binary search may produce incorrect results.

Certainly! Here's an implementation of the binary search algorithm in C, using two different methods for comparison:

Method 1: Recursive Binary Search

#include <stdio.h>

int binarySearchRecursive(int arr[], int low, int high, int target) {
    if (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            return binarySearchRecursive(arr, mid + 1, high, target);
        else
            return binarySearchRecursive(arr, low, mid - 1, target);
    }

    return -1;
}

int main() {
    int arr[] = {2, 4, 7, 10, 14, 20, 23};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 14;
    int result = binarySearchRecursive(arr, 0, n - 1, target);

    if (result == -1)
        printf("Element not found\n");
    else
        printf("Element found at index %d\n", result);

    return 0;
}        

Method 2: Iterative Binary Search

#include <stdio.h>

int binarySearchIterative(int arr[], int low, int high, int target) {
    while (low <= high) {
        int mid = low + (high - low) / 2;

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

    return -1;
}

int main() {
    int arr[] = {2, 4, 7, 10, 14, 20, 23};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 14;
    int result = binarySearchIterative(arr, 0, n - 1, target);

    if (result == -1)
        printf("Element not found\n");
    else
        printf("Element found at index %d\n", result);

    return 0;
}        

In binary search, the best case and worst case scenarios refer to the situations that lead to the most favorable and least favorable performance of the algorithm, respectively.

Best Case:

The best-case scenario in binary search occurs when the target element is found exactly in the middle of the array. In this case, the algorithm can determine the target element in the first comparison and return the index immediately. The best-case time complexity of binary search is O(1), indicating constant time complexity.

Worst Case:

The worst-case scenario in binary search happens when the target element is either the first element or the last element in the array, or when the target element is not present in the array at all. In these cases, the algorithm needs to repeatedly divide the search space until it reaches a single element or determines that the target element is not present. The worst-case time complexity of binary search is O(log n), where n is the number of elements in the array. This logarithmic time complexity indicates that the search time grows slowly as the size of the array increases.

It's important to note that the average case time complexity of binary search is also O(log n), assuming a uniformly distributed target element. This means that on average, binary search performs logarithmically with respect to the number of elements in the array.