/*

Binary search

Given a list of integers of length len, and a key, determine if key is
present in list and return the index of key.   If not present, return -1

Pre Conditions:
list is sorted in ascending order

*/

int bsearch_int(int list[], int len, int key) {
    int low = 0;
    int high = len;

    int probe;

    /* invariant: 
        If present, key is in the index range [low, high), 
        i.e. key is one of list[low], ..., list[high-1]

    */

    /* keep searching until the search interval is empty */
    while ( low < high ) {
        /* pick a probe point in the middle of the interval
           we assume we do not get integer overflow here, which is safe
           to assume on the Arduino

           Invariant: low <= probe < high
        */
        probe = (high + low) / 2;

        if ( key == list[probe] ) {
            /* found it */
            return probe;
            }

        /* determine which side of probe the key might lie */
        if ( key < list[probe] ) {
            high = probe;
            }
        else {
            low = probe + 1;
            }
        
        } // keep looking

    /* if the search interval is empty, the key is not present */
    return -1;
    }