Homework 1

CS23

40 pts., due Feb. 21

1. (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
   This part will be turned-in in class. You should use a word processor or text editor for this.

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