Understanding Binary Search

Binary Search is an efficient algorithm for finding an item from a sorted array. It works by repeatedly halving the search interval:

1. Compare the target value with the middle element mid.
2. If match, return the index.
3. If target is smaller, continue search in the left half.
4. If target is larger, continue search in the right half.

---

Complete C Implementation

c (ISO Standard)
Run in Compiler.cCopy
#include <stdio.h>

/* Iterative Binary Search with overflow-safe mid calculation */
int binarySearchIterative(const int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2; /* Prevents (low + high) integer overflow */

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

int main() {
    int sortedData[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(sortedData) / sizeof(sortedData[0]);

    int key = 23;
    int result = binarySearchIterative(sortedData, n, key);

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

    return 0;
}

Sample Output

text (ISO Standard)
Copy
Element 23 found at index 5.

---

Complexity Analysis

• Time Complexity: O(log n) across all cases.
• Space Complexity: O(1) for iterative, O(log n) stack depth for recursive.
• Prerequisite: The input array must be sorted.

---

Related Programs

• Compare with sequential search in Linear Search in C.
• Sort arrays before searching using Bubble Sort in C.