Lintcode: Search Insert Position

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.

Have you met this question in a real interview? 

Yes

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

Tags Expand 

Binary Search Sorted Array Array

Simple binary search.
Note the last step of while loop is always when start = end.
When the loop finishes, the start always stay at the position that element > target.
while end may be at the edge position that element < or > targe
Even middle cannot be used: when start = end, middle = (start + end) /2 = start = end. However, we don't know whether middle is the left or right edge at this time. Then start or end changes based on A[mid] value, and while loop stops. So we cannot get final result through mid.

class Solution {
    /** 
     * param A : an integer sorted array
     * param target :  an integer to be inserted
     * return : an integer
     */
public:
    int searchInsert(vector<int> &A, int target) {
        // write your code here
        int start = 0;
        int end = A.size() - 1;
        //int mid = (start + end) / 2;;
        while(start <= end){
            int mid = (start + end) / 2;
            if(A[mid] > target) end = mid - 1;
            else if(A[mid] < target) start = mid + 1;
            else return mid;
        }
        return start;
    }
};