CSCE 322 Chapter 3 Supplementary Homework Exercise
Due Monday, Feb 22, 1999

Consider the following pseudocode for a binary search:

{X ranges 1 to N of integers sorted in increasing order}
{N >= 1 is top possible index for searching}
{T is the search key}
{BinSearch returns the index where T is found, or 0 if not exist}

int BinSearch (int array X, int N, int T)
    int lo = 1
    int hi = N
    while lo <= hi do
        int mid = (lo + hi) / 2
        if x[mid] <= T then lo = mid + 1
        if x[mid] >= T then hi = mid - 1
    end while
    return ????
end BinSearch

Flesh out this algorithm with assertions to determine and prove 
a simple arithmetic expression (using only arithmetic operators)
for the return value.