Binary search

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

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


Back to list of assignments