sundeepblue
3/23/2014 - 2:26 AM

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inse

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Search In Sorted Array.cpp
content_copyfile_download
int search_insert(vector<int> A, int target) {
    if(A.empty()) return -1;
    if(target < A[0] || target > A[A.size()-1]) return -1;
    int low = 0, high = A.size()-1;
    while(low <= high) {
        int mid = low + (high-low)/2;
        if(target == A[mid]) return mid;
        if(target < A[mid]) high = mid - 1;
        else low = mid + 1;
    }
    return low;         // gist, should return low if not find
}