int binsearch(int A[], int low, int high, int key) {
    int L = low, U = high, M;
    while (L <= U) {
        /* Invariant: A[low]..A[L-1] all < key, A[U+1]..A[high] all >= key;
                      also L <= U + 1 */
        M = (L + U) / 2; /* M must be in range L...U (property of mean) */
        if (A[M] < key) {
            /* Here, A[low]..A[M] all < key (because array is ordered) */
            L = M + 1;   /* Re-establish invariant, L cannot exceed U+1 */
        } else {
            /* Here, A[M]..A[high] all >= key */
            U = M - 1;   /* Re-establish invariant, U cannot be below L-1 */
        }
    }
    /* Here L <= U + 1 (from invariant), and L > U (loop termination),
       therefore L == U + 1, so:
       A[low]..A[L-1] all < key, and A[L]..A[high] all >= key,
       therefore L is the subscript of the first non-lesser element. */
    return L;
}

/* Short main function for testing... */
#include <stdio.h>
int test[] = {1,1,3,5,5,6,8,9,9};
#define high 8     /* NB: This is the subscript of the last array element */

main() {
    int j, i;
    for (i=0; i<=high; i++) {
        printf("A[%d]=%d ", i, test[i]);
    }
    putchar('\n');
    for (i=0; i<=10; i++) {
        j = binsearch(test, 0, high, i);
        if (j > 0 && test[j-1] >= i  ||  j <= high && test[j] < i) {
            printf("ERROR! ");
        }
        if (j <= high && test[j] == i) {  /* Note test for item i found. */
            printf("Seeking %2d, found at j=%2d:\n", i, j);
        } else {
            printf("Seeking %2d, NOT found at j=%2d:\n", i, j);
        }
        if (binsearch(test, i, i-1, 5) != i) {
            printf("NULL SEARCH ERROR: %d\n", i);
        }
    }
    return 0;
}