LeetCode35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

二分法查找

题目提示，在数组中非数组外寻找，应设置right = nums.length - 1。本题中应该先对题目进行特殊处理，考虑target大于数组中最大数字的情况，因此增加示例代码1中的判断。或者将特殊情况合并，设置right = nums.length，省去特殊处理，如示例代码2。
讨论：
情况一：数组中无目标值，找到第一个大于target的数字并返回其索引。
情况二：数组中有目标值，找到第一个等于target的数字并返回其索引。
合并为position（target）<= nums[target]

class Solution {
    //target放在第一个它<=的数字前面
    public int searchInsert(int[] nums, int target) {
        //特殊处理
        if (target > nums[nums.length - 1]) {
            return nums.length;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
           int mid = left + (right - left) / 2;
            if (target <= nums[mid]) {
               right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        return left;
    }
}

public class Solution {
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        int left = 0;
        int right = len;
        // 在区间 nums[left..right] 里查找第 1 个大于等于 target 的元素的下标
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target){
                // 下一轮搜索的区间是 [mid + 1..right]
                left = mid + 1;
            } else {
                // 下一轮搜索的区间是 [left..mid]
                right = mid;
            }
        }
        return left;
    }
}