Binary search in C locates a target in a sorted array by repeatedly discarding half of the remaining candidates. This iterative implementation uses an overflow-resistant midpoint formula and returns a zero-based index or -1 when the target is absent.
How does binary search in C work iteratively?
For binary search C code, the loop tracks the active range with low and high. It checks the middle element, then moves the appropriate bound inward. The update must use mid + 1 or mid – 1 so the already-checked midpoint is not examined again.
Complete program:
#include <stdio.h>
int binary_search(const int a[], int n, int target) {
int low = 0, high = n – 1;
while (low <= high) {
int mid = low + (high – low) / 2;
if (a[mid] == target) return mid;
if (a[mid] < target) low = mid + 1;
else high = mid – 1;
}
return -1;
}
int main(void) {
int values[] = {3, 8, 12, 17, 21, 21, 34, 50};
int n = sizeof values / sizeof values[0];
int tests[] = {3, 50, 17, 21, 13};
size_t count = sizeof tests / sizeof tests[0];
for (size_t i = 0; i < count; i++) {
int index = binary_search(values, n, tests[i]);
printf(“target %d: %d\n”, tests[i], index);
}
return 0;
}
What do sorted input, bounds, and return values mean?
The array must be sorted in ascending order. Without sorted input or another ordering guarantee, binary search cannot decide which half to discard; sort the data first when necessary.
low is the first possible index, and high is the last possible index. The initial range is from 0 through n – 1. The midpoint is calculated as low + (high – low) / 2, rather than (low + high) / 2, reducing the risk of integer overflow for large indexes.
This function returns the matching zero-based index immediately. If no candidate remains, low > high and the function returns -1. With duplicate values, it may return any matching occurrence; it does not promise the first or last duplicate.
How do you trace and test found and absent targets?
Using the sample array, trace a found target of 34:
- low = 0, high = 7, mid = 3: value 17 is less than 34, so set low to 4.
- low = 4, high = 7, mid = 5: value 21 is less than 34, so set low to 6.
- low = 6, high = 7, mid = 6: value 34 matches, so return index 6.
For an absent target of 13:
- Midpoint 3 contains 17, so high becomes 2.
- Midpoint 1 contains 8, so low becomes 2.
- Midpoint 2 contains 12, so low becomes 3.
- Now low is 3 and high is 2, so the function returns -1.
The program tests the first element (3), last element (50), middle element (17), a duplicate (21), and an absent target (13). Expected results are indexes 0, 7, 3, 5, and -1 respectively for this implementation.
How does C binary search compare with recursion, and what is its complexity?
A recursive version makes the shrinking range explicit but adds function-call overhead. It uses the same midpoint calculation and return convention:
int binary_search_recursive(const int a[], int low, int high, int target) {
if (low > high) return -1;
int mid = low + (high – low) / 2;
if (a[mid] == target) return mid;
if (a[mid] < target)
return binary_search_recursive(a, mid + 1, high, target);
return binary_search_recursive(a, low, mid – 1, target);
}
Call it with binary_search_recursive(values, 0, n – 1, target). Both iterative and recursive binary search run in O(log n) time because each comparison halves the remaining range. The iterative form uses O(1) extra space; recursion uses O(log n) stack space.