Binary search

Challenge

Find a target in a sorted array in O(log n) by repeatedly halving the search range.

Task

Implement long binary_search(const int *a, size_t n, int target) returning the index of target in the ascending-sorted array a, or -1 if it is not present. No main — the grader calls it.

Input

• a: an array of int sorted in ascending order.
• n: the number of elements (may be 0).
• target: the value to locate.

Output

The index of target as a long, or -1 if absent. If duplicates exist, any matching index is acceptable.

Example

binary_search({1,3,5,7,9,11,13}, 7, 1)    ->   0
binary_search({1,3,5,7,9,11,13}, 7, 13)   ->   6
binary_search({1,3,5,7,9,11,13}, 7, 6)    ->   -1
binary_search(a, 0, 5)                     ->   -1

Edge cases

• Empty array (n = 0) returns -1.
• Targets below the smallest or above the largest return -1.

Rules

• Run in O(log n); compute mid as lo + (hi - lo)/2 to avoid overflow. The array is assumed sorted.

Input format

A sorted int array a, its length n, and the target value.

Output format

The index of target as a long, or -1 if not present.

Constraints

Array is sorted ascending; run in O(log n).

Starter code

#include <stddef.h>

long binary_search(const int *a, size_t n, int target) {
    /* TODO */
    return -1;
}