12 Feb 1996

Outline

• Solving quiz problem 2 using loop invariants
• Using arrays to simplify programs

Solving quiz problem 2 using loop invariants

The following routine correctly performs a binary search.

// A is the array (of non-negative integers)
// len is the length of A
// key is what we're looking for

int
bsearch(int A[], int len, int key) {
    int bottom = 0, top = len - 1, mid;
    while(bottom <= top) {
        mid = (bottom + top) / 2;
        if(A[mid] == key) return mid;
        if(key < A[mid]) top = mid - 1;
        else bottom = mid + 1;
    }
    return -1; // not found
}

1. The while test is changed to ``while (bottom < top)''.
2. The line ``if(key < A[mid]) top = mid-1;'' is changed to ``if(key < A[mid]) top = mid;''.
3. The line ``mid = (bottom + top) / 2;'' is changed to ``mid = (bottom + top + 1)/2;''.

Suppose that the author of this routine had considerately left us the following comment:

// Loop invariants:
// 1) At the beginning of each iteration, the search key either
//    is not present in the array, or lies between positions
//    bottom and top (inclusive).
// 2) In each iteration, top-bottom+1 (the number of possible positions
//    for key) decreases.

Now show how each of the suggested changes either causes a violation of the invariants, or leaves them intact.

Using arrays to simplify programs

Here is a neat way of using arrays to simplify programs. Not especially relevant to THIS assignment, but nice idea to keep in the back of your mind.

This example is taken from Danny Sleator's internet chess server. The problem being solved is simply to determine the value of a chess position for White and Black. A pawn is worth 1, a knight and bishop are each worth 3, a rook is worth 5, and a queen is worth 9.

One way to solve the problem is to have a loop checking all the entries, and for each one, to have a big ``if'' or ``case'' statement that adds the appropriat enumber depending on the value. But this is really long and messy.

(Here is actual code that somebody wrote to solve this problem in that way. The contents of a square is encoded by the appropriate piece type, plus MIDDLE if the piece is black.

#define EMPTY    0
#define PAWN     1
#define KNIGHT   2
#define BISHOP   3
#define ROOK     4
#define QUEEN    5
#define KING     6
#define BLACK    0
#define WHITE    1
#define MIDDLE  10

int
material_strength(int num, int *wv, int *bv) {
    char            x, y, tmp, value;

    if (wv == NULL || bv == NULL)
        return -1;
    *wv = 0;
    *bv = 0;
    for (y = 0; y < 8; y++) {
        for (x = 0; x < 8; x++) {
            value = Game[num].board[x][y];
            if (Game[num].board[x][y] > MIDDLE)
                value -= MIDDLE;
            switch (value) {
            case PAWN:
                tmp = 1;
                break;
            case KNIGHT:
            case BISHOP:
                tmp = 3;
                break;
            case ROOK:
                tmp = 5;
                break;
            case QUEEN:
                tmp = 9;
                break;
            default:
                tmp = 0;
                break;
            }
            if (Game[num].board[x][y] > MIDDLE)
                *bv += tmp;
            else
                *wv += tmp;
        }
    }
    return 0;
}

Here is the much simpler new version of the code. Here we use an array to store all the piece values. Note that there are no special cases here. All that is encoded into the array. The method does however depend on the fact that BLACK is zero and WHITE is one and the values of PAWN, etc. do not change.

char piece_value[2][17] =
        {{0,0,0,0,0,0,0,0,0,0,0,1,3,3,5,9,0},  /* black first */
            {0,1,3,3,5,9,0,0,0,0,0,0,0,0,0,0,0}}; /* then white  */

int
strength(board_t board, int color) {
    int x, y, ret;
    ret = 0;
    for(x = 0; x < 8; x++)
    for(y = 0; y < 8; y++) {
        ret += piece_value[color][board[x][y]];
    }
    return ret;
}