Exercise 3-1

There are three scenarios for when we check a number: it is greater than v[mid], less than v[mid], or equal to v[mid]. Currently, we have tests for each scenario, but we can combine the latter two. Now, if the number is greater than v[mid], we update low to mid-1, but in both other cases, we update high to mid. We also update the condition of the while-loop to low < high because now low and high could be equal if the number is found. Once we exit the loop, we check if v[low] is equal to x; if it is, we return low, but otherwise, we return -1.

    /* binsearch:  find x in v[0] <= v[1] <= ... <= v[n-1] */
    int binsearch(int x, int v[], int n)
    {
        int low, high, mid;
    
        low = 0;
        high = n - 1;
        while (low <= high) {
        while (low < high) {
            mid = (low+high) / 2;
            if (x < v[mid])
                high = mid - 1;
            else if (x > v[mid])
                low = mid + 1;
            else    /* found match */
                return mid;
            if (x <= v[mid])
                high = mid;
            else
                low = mid + 1;
        }
        return -1;  /* no match */
        return (v[low] == x) ? low : -1;
    }

After timing both versions on various tests, suprisingly, the initial version was on average 6% faster! This is because in our version, when x is found, we do not always immediately return unlike the original version. This may be a scenario where the book shows its age. Back in the day, computers were much slower than they are today and perhaps minimizing checks would have outweighed the downside of requiring more iterations on certain inputs.

Note: if you want to time the program yourself, you can use the time command found on various *nix systems. Better yet, try combining it with the for-loop in your shell (e.g. for i in {1..10}; do time ./execname; done in bash times the program 10 times) to test it multiple times so you can find the average time.