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;
}

Common mistakes

Off-by-one in low/high boundary updates; integer overflow in (low + high) / 2 instead of low + (high - low) / 2; infinite loop when bounds don't progress.

Edge cases to handle

Empty array; target element not present; target at index 0 or index len-1; array with all identical elements.