Recursive binary search

Challenge

Implement:

int binary_search(const int *a, int n, int target);

Recursively search the sorted (ascending, distinct) array for target. Return an index where it occurs, or -1.

Input format

Sorted a, length n, target.

Output format

An index of target, or -1.

Constraints

Recurse on the correct half.

Starter code

#include <stddef.h>
/* Recursive binary search in a sorted (ascending, distinct) array. Return an index of target, or -1. */
int binary_search(const int *a,int n,int target){ (void)a;(void)n;(void)target; return -1; }

Common mistakes

Integer overflow in (lo+hi)/2; recursing on the wrong half.

Edge cases to handle

Empty range returns -1.

Background lessons

• Divide and conquer