Search Insert Position

Description

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.

You may assume NO duplicates in the array.

Example
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Challenge
O(log(n)) time Using binary search, we have met

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
    /** 
     * param A : an integer sorted array
     * param target :  an integer to be inserted
     * return : an integer
     */
public:
    int searchInsert(vector<int> &nums, int target) {
        // write your code here
        // o(n)
        // if( nums.empty() || target <= nums[0] ) {
        //     return 0;
        // }
        // for ( int i = 0; i < nums.size(); ++i ) {
        //     if ( target <= nums[i]  ) {
        //         return i;
        //     }
        // }
        // return nums.size();
        // o(logn)
        if( nums.empty() ){
            return 0;
        }
        int start = 0;
        int end = nums.size() - 1;
        while( start + 1 < end ) {
            int mid = start + ( end - start ) / 2;
            // when the target is sure in the left region
            // we want to find the first pos, so selecting left
            if ( target <= nums[mid] ) {
                end = mid;
            }
            // when the target is in the right region
            // targe > nums[mid]
            else {
                start = mid;
            }
        }
        // target in the left exceeding 0 of nums, or in the start
        if( target <= nums[start] ) {
            return start;
        }
        // target in the middle of start and end, or in the end
        if( target <= nums[end] ){ 
            return end;
        }
        //target in the right exceeding size of nums
        return nums.size();
    }
};

Similar problems

x

Tags

x