给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。

示例 1:
输入: [1,3,5,6], 5输出: 2
示例 2:
输入: [1,3,5,6], 2输出: 1
示例 3:
输入: [1,3,5,6], 7输出: 4
示例 4:
输入: [1,3,5,6], 0输出: 0

public int SearchInsert(int[] nums, int target) {
    if(nums == null || nums.Length == 0) return 0;

    int start = 0;
    int end = nums.Length - 1;
    int result = -1;
    int tempIndex = -1;

    while(start <= end)
    {
        //二分法查找位置
        tempIndex = (end + start)/2;
        if(nums[tempIndex] == target)
        {
            return tempIndex;//找到匹配
        }

        if(target > nums[tempIndex])
        {
            //去右边那半
            start = tempIndex + 1;
        }
        else
        {
            //去左边那半
            end = tempIndex - 1;
        }
    }

    //没找到匹配就是start了
    return start;
}

看似简单，其实要考虑很多情况的，start是一个往上加的指标，而目的是找一个刚好比target大的值或者是数组尾部的下一位的位置，在两指标重合时，无论是比target值大的end--，还是比target值小的start++，start值总是那个比target大的指标。所以，最后没找到的情况下，返回start指标就是要插入的位置。