Following up on the class discussion of insertion sort, please write C code decorated with assertions for a binary-search function with this prototype:
int *binsearch(int needle, int *haystack, int n);
where
haystack
is a sorted array of length n
.needle
appears anywhere in haystack
, binsearch
returns a pointer to a location in haystack
containing needle
.needle
appears nowhere in haystack
, binsearch
returns NULL
.haystack
are unchanged.Please write precondition, postcondition, loop invariants, and any intermediate assertions you need to get working. The loop invariant can be hard to get right; you'll want to pay close attention.
The running time of your function should be O(log n).
In time for class on Wednesday, March 10, please
SORTED[x..y)