35. 搜索插入位置

题意：

解题思路：

思路：二分查找，
1. 如果存在，则必然有值，返回对应下标即可；
2. 如果不存在则返回顺序插入的位置；
    2.1 通过二分每次排除一半的数字，如果目标值小于中间值，则肯定在中间值左侧，反之在右侧；
    2.2 直到low > high 最终返回low

PHP代码实现：

class Solution {
    function searchInsert($nums, $target) {
        if ($nums == null) return -1;
        $low = 0;
        $high = count($nums) - 1;
        while ($low <= $high) {
            $mid = $low + floor(($high - $low) / 2);
            if ($target < $nums[$mid]) {
                $high = $mid - 1;
            } else if ($target > $nums[$mid]) {
                $low = $mid + 1;
            } else {
                return $mid;
            }
        }
        return $low;
    }
}

GO代码实现：

func searchInsert(nums []int, target int) int {
    left :=0
    right := len(nums) - 1
    mid := 0
    for left <= right {
        mid = (left + right) / 2 
        if nums[mid] == target {
            return mid
        } else if nums[mid] > target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    } 
    return left
}