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: 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;
    }
    



Thomas P. Kelliher
Sat Mar 2 15:41:16 EST 1996
Tom Kelliher