题解 | #搜索插入位置#

题目描述：给出一个有序的数组和一个目标值，如果数组中存在该目标值，则返回该目标值的下标。如果数组中不存在该目标值，则返回如果将该目标值插入这个数组应该插入的位置的下标。假设数组中没有重复项。
下面给出几个样例：
        [10,30,50,60], 50 → 2
        [10,30,50,60], 20 → 1
        [10,30,50,60], 70 → 4
        [10,30,50,60], 0 → 0
示例1:
        输入：[10,30,50,60],50
        返回值：2
思路：要想搜索target值对应的插入位置，由于题目明确告诉我们数组有序，那么直接一维查找从小到大，一旦寻找到target值则返回下标，如果找不到（A[i]<target）则令flag = i+1,这样可以将插入位置不断后移，直到第一个比target大的值中断循环即可。具体代码如下：

class Solution {
public:
    /**
     * 
     * @param A int整型一维数组 
     * @param n int A数组长度
     * @param target int整型 
     * @return int整型
     */
    int searchInsert(int* A, int n, int target) {
        // write code here
        if(n <=0) return -1;
        else if(target < A[0]) return 0;
        else if(target > A[n-1]) return n;
        else
        {
            int flag = -1;
            for(int i=0;i<n;i++)
            {
                if(A[i] < target)
                {
                    flag = i+1;
                }
                if(A[i] == target)
                {
                    flag = i;
                    break;
                }
            }
            return flag;
        }
    }
};