**CS23**

**40 pts., due Feb. 21**

- (10 pts.) Write, in C or C++, a version of the
*non-recursive*binary search algorithm for integers. Then:- Write pre- and post-conditions for your function
- Write invariants for any loops (one per loop) you utilized

/* pre-condition: array has at least len values which have been sorted into ascending order post-condition: the index of target in array is returned, or -1 if target is not in array */ int binsearch(int array[], int target, int len) { int f = 0; // index of first place target might be int l = len - 1; // index of last place target might be int mid // invariant: target might be in array[f]...array[l] the distance // between f and l decreases by half after each iteration while (f <= l) { mid = (f + l) / 2; if (target == array[mid]) return mid; else if (target < array[mid]) l = mid - 1; else s = mid + 1; } return -1; }

Sat Mar 2 15:41:16 EST 1996