Binary search in C
Find a key in a sorted array. Compare the key with the middle item, and keep only the half that can hold the key.
- File
binary_search.c, 19 lines- Level
- Native tests
- pass in this build
- Toolchain
- C23, GCC 15 or Clang 21, with ASan and UBSan
- Test framework
- assert
- Run the tests
cc -std=c2x -Wall -Wextra -Wpedantic -Werror -fsanitize=address,undefined *.c && ./a.out
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.
#include "binary_search.h"
ptrdiff_t binary_search(const int64_t *a, size_t n, int64_t x) {
size_t lo = 0, hi = n; // @line L1
while (lo < hi) { // @line L2
size_t mid = lo + (hi - lo) / 2; // @line L3
if (a[mid] < x) { // @line L4
lo = mid + 1; // @line L5
} else if (a[mid] > x) { // @line L6
hi = mid; // @line L7
} else {
return (ptrdiff_t)mid; // @line L8
}
}
return -1; // @line L9
}
binary_search.h 13 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.
#ifndef BINARY_SEARCH_H
#define BINARY_SEARCH_H
#include <stddef.h>
#include <stdint.h>
// binary_search returns an index i with a[i] == x, or -1 when x is not in a[0..n-1]. The array must be sorted.
ptrdiff_t binary_search(const int64_t *a, size_t n, int64_t x);
#endif
test_binary_search.c 43 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "binary_search.h"
static int cmp(const void *p, const void *q) {
int64_t a = *(const int64_t *)p, b = *(const int64_t *)q;
return (a > b) - (a < b);
}
int main(void) {
const int64_t a[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
assert(binary_search(a, 10, 23) == 5);
assert(binary_search(a, 10, 2) == 0);
assert(binary_search(a, 10, 91) == 9);
assert(binary_search(a, 10, 30) == -1);
assert(binary_search(a, 10, 1) == -1);
assert(binary_search(a, 10, 100) == -1);
assert(binary_search(NULL, 0, 1) == -1);
srand(2150);
int64_t b[30];
for (int t = 0; t < 2000; t++) {
size_t n = (size_t)(rand() % 31);
for (size_t i = 0; i < n; i++) b[i] = rand() % 41 - 20;
qsort(b, n, sizeof b[0], cmp);
int64_t x = rand() % 51 - 25;
ptrdiff_t got = binary_search(b, n, x);
int found = 0;
for (size_t i = 0; i < n; i++) found |= b[i] == x;
if (found) {
assert(got >= 0 && (size_t)got < n && b[got] == x);
} else {
assert(got == -1);
}
}
puts("ok");
return 0;
}
What the next level needs
- I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work