Sorted Search, No Size

You are given an array-like data structure Listy which lacks a size method. It does, however, have an elementAt(i) method that returns the element at index i in O(1) time. If i is beyond the bounds of the data structure, it returns -1. (For this reason, the data structure only supports positive integers.) Given a Listy which contains sorted, positive integers, find the index at which an element x occurs. If x occurs multiple times, you may return any index.

Solution

/**
 * 每次放大一倍找到长度,然后二分
 */
int search(Listy list, int value){
    int index = 1;
    while (list.elementAt(index) != -1 && list.elementAt(index) < value){
        index *= 2;
    }
    return binarySearch(list, value, index / 2, index);
}

int binarySearch(Listy list, int value, int low, int high){
    int mid;

    while (low <= high){
        mid = (low + high) / 2;
        int middle = list.elementAt(mid);
        if (middle  > value || middle == -1){
            high = mid - 1;
        }
        else if (middle < value ){
            low = mid + 1;
        }
        else {
            return mid;
        }
    }
    return -1;
}