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.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

tag: binary search

常规的二分查找，如果没有找到(i == j)，则判断A[i]与target的大小，分情况插入i位或i+1位。如果i==n，要单独判断。

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        int i = 0;
        int j = n;
        while(i < j){
            int mid = (i + j) / 2;
            if(A[mid] == target){
                return mid;
            }
            if(A[mid] < target){
                i = mid + 1;
            }
            else{
                j = mid;
            }
        }
        if(i == n){
            return n;
        }
        if(A[i] < target){
            return i + 1;
        }
        else{
            return i;
        }
    }
};