C binary search and the standard bsearch
Binary search works on a sorted array. It compares the target with the middle element and discards the half that cannot contain it, so a range of n elements needs at most about log2(n) + 1 comparisons. The middle is computed as low + (high - low) / 2, which cannot overflow, unlike (low + high) / 2.
C
#include <stdio.h>
#include <stdlib.h>
static int binary_search(const int *a, int n, int key, int *steps) {
int low = 0, high = n - 1;
*steps = 0;
while (low <= high) {
(*steps)++;
int mid = low + (high - low) / 2;
if (a[mid] == key) {
return mid;
}
if (a[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
static int compare_ints(const void *x, const void *y) {
int a = *(const int *)x;
int b = *(const int *)y;
return (a > b) - (a < b);
}
int main(void) {
int primes[] = {2, 3, 5, 7, 11, 13, 17, 19};
int n = (int)(sizeof primes / sizeof primes[0]);
int steps;
int index = binary_search(primes, n, 11, &steps);
printf("11: index %d in %d steps\n", index, steps);
index = binary_search(primes, n, 4, &steps);
printf("4: index %d in %d steps\n", index, steps);
int key = 17;
int *found = bsearch(&key, primes, (size_t)n, sizeof primes[0], compare_ints);
printf("bsearch finds 17 at index %d\n", found ? (int)(found - primes) : -1);
return 0;
}