Search a Sorted Array of Unknown Length

EPI 25.15

Description:

Search in sorted array. Array length unknown.

Example:

Note

Idea:

先确定left, right，然后在这个区间内找。

time: O(logn)

Code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int searchUnbounded(vector<int> arr, int k){
    int p=0;
    while(true){
        try{
            int idx = (1<<p)-1; // 2^p - 1
            if(arr.at(idx)==k){
                return idx;
            }
            else if(arr.at(idx)>k){
                break;
            }

        } catch(const exception& e){
            break;
        }
        ++p;
    }
    // inclusive search
    int left = max(0, 1<<(p-1)); // 2^(p-1)
    int right = (1<<p) - 2; // 2^p - 2
    while(left<=right){
        int mid = left + (right-left)/2;
        try{
            if(arr.at(mid)==k){
                return mid;
            }
            else if(arr.at(mid)>k){
                left = mid+1;
            }
            else{
                right = mid-1;
            }

        } catch(const exception &e){
            right = mid-1;
        }

    }
    return -1;

}

int main(){
    vector<int> arr={1,2,3,4,5};
    cout<<searchUnbounded(arr, 2);
}