Binary search

Challenge

Find a value in a sorted array by repeatedly halving the search range.

Task

Implement int binary_search(const int *a, int n, int target) on a sorted (ascending) array. Return an index where target is found, or -1 if it is absent.

Input

• a: array of n ints sorted in ascending order (read-only).
• n: the number of elements.
• target: the value to search for.

Output

int: an index i with a[i] == target, or -1 if target is not present.

Example

a={1,3,5,7,9,11}, target=7    ->   3
a={1,3,5,7,9,11}, target=1    ->   0
a={1,3,5,7,9,11}, target=8    ->   -1  (absent)

Edge cases

• An absent target returns -1.
• Works on the first and last elements.

Rules

• The input is assumed sorted ascending; use it to halve the range each step (O(log n)).

Input format

a: n ints sorted ascending; n; target.

Output format

int: an index of target, or -1 if absent.

Constraints

Input is sorted ascending; halve the range each step.

Starter code

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