力扣Hot100——35.搜索插入的位置（二分查找）

除暴力循环，更好的办法是二分查找，降低查询次数。

二分查找思想

如果一个问题，待查找的数是一个整数，且知道范围，大概就可以使用二分查找算法。

1. 设置 left 、 right 与mid 分别标示数组的头、尾以及中间位置
2. 每次根据 nums[mid] 与 target 之间的大小进行判断，相等直接返回 mid，若 nums[mid] < target 则 left 右移至 mid+1 ；若 nums[mid] > target 则 right 左移至 mid-1
3. 查找结束，如果没有相等则返回 left，该值为插入位置下标
4. 循环退出条件为 left > right

public int searchInsert(int[] nums, int target) {
    // 二分查找法
    int left = 0, right = nums.length - 1;
    while(left <= right){
        int mid = (left + right) >> 1;
        if(nums[mid] == target){
            return mid;
        }
        else if(nums[mid] < target){
            left = mid + 1;
        }
        else{
            right = mid - 1;
        }
    }
    return left;
}

还有一种修改的方式为，将 nums[mid] == target 的情况与 nums[mid] == target 放在一起处理。这样做，在两数相等的时候会错过一次输出，但是在下一次循环的时候，left一定会大于 right，并且 left 指向的就是 target。也就是多循环了一次，少了一些判断。

public int searchInsert(int[] nums, int target) {
    // 二分查找法
    int left = 0, right = nums.length - 1;
    while(left <= right){
        int mid = (left + right) >> 1;
        if(nums[mid] < target){
            left = mid + 1;
        }
        else{	//将 nums[mid] < target 放在这里处理
            right = mid - 1;
        }
    }
    return left;
}