Binary Search

Binary Search

Binary search is a highly efficient searching algorithm used to find a target value within a sorted array or list. It operates by repeatedly dividing the search interval in half until the target value is found or the interval is empty.

Here’s how the binary search algorithm works:

1. Initialize pointers: Set two pointers, left and right, to the first and last elements of the array, respectively.
2. Midpoint calculation: Calculate the midpoint of the array as (left + right) / 2.
3. Compare with the midpoint: Compare the target value with the value at the midpoint.
4. Adjust pointers: If the target value matches the midpoint value, the search is complete. If the target value is less than the midpoint value, set right = mid - 1 to search the left half of the array. If the target value is greater than the midpoint value, set left = mid + 1 to search the right half of the array.
5. Repeat: Repeat steps 2-4 until the target value is found or until left is greater than right.

Binary search is a divide-and-conquer algorithm that halves the search space at each step. As a result, it has a time complexity of O(logn), where n is the number of elements in the array or list.

Here’s a simple implementation of binary search in C:

#include <stdio.h>

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // Check if target is present at mid
        if (arr[mid] == target)
            return mid;
        // If target greater, ignore left half
        if (arr[mid] < target)
            left = mid + 1;
        // If target is smaller, ignore right half
        else
            right = mid - 1;
    }
    // If target is not present in array
    return -1;
}

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

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

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

    return 0;
}

Output:

Element 9 found at index 3

Time Complexity

The time complexity of binary search is O(logn), where n is the number of elements in the array or list being searched.

Here’s why the time complexity is O(logn):

• In each step of binary search, the algorithm divides the search interval in half.
• This halving of the search interval effectively reduces the size of the search space by half with each comparison.
• As a result, the algorithm can quickly home in on the target element, especially in large datasets.
• The logarithmic time complexity O(logn) arises because the algorithm performs at most log2​n comparisons, where n is the number of elements in the array or list.
• Even for very large datasets, binary search can efficiently locate the target element in a relatively small number of comparisons.

Note: When writing time complexity using Big O notation we could also just have written O(logn), but O(log2n) reminds us that the array search area is halved for every new comparison, which is the basic concept of Binary Search, so we will just keep the base 2 indication in this case.