Unknown size position of target

streaming flow; 反向binary search

Problem:

find the target if we don't know the array's size.

Solution:

• MyArray is a class, since it is customized, and we don't know the length of array

• use long as output, since the length of array is unknown, maybe it too big.

• since we just want to find the value, so use left <= right

• for // here, we can only make sure target is between the interval from left to right.

public long unknownSize(MyArray myArray, int target){
    //corner case
    int left = 0, right = 1;
    while(myArray.get(end) != null && myArray[right] < target){
        left = right;
        right *= 2;
    }
    //
    while(left <= right){
        int mid = left + (right - left) /2;
        if(myArray.get(mid) != null &myArray.get(mid) == target) return mid;
        if(myArray.get(mid) != null &myArray.get(mid) < target)){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    return -1;
}