搜索插入位置

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

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4

提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的 升序 排列数组
-104 <= target <= 104

使用递归求解

思路：题目中说已经排序，所以直接使用二分法查找 二分思路：

1. 数组的中间的数，分为奇数个数组和偶数个数组，不用纠结奇数个直接是中间的数，偶数固定取中间靠前位置或取靠后位置，保持统一即可。
2. 如果取到中间位置的值跟查找的数一致，直接返回报告查找到
3. 如果取到中间位置的值大于目标值，则目标值在这个值的前面，进入下一次从步骤1用数组开始到中间值减一再找一次
4. 如果取到中间位置的值小于目标值，则目标值在这个值的后面，进入下一次从步骤1中间值加一到数组结束再找一次

递归出口：

1. 如果找到值，返回目标值的下标
2. 如果这个左边标记大于右边标记，表示数组都已判断完成没有符合条件的数据，返回左边标记

返回左边原因：

• 到达临界值时（左边等于右边），如果临界值大于查找目标值，会用右边减一去下一次查找。此时左边标记对应的值是大于目标值的，如果要给数组插入目标值就会插入在这个位置上，把这个位置后的全部数据向后移动一位，所以可以返回左边标记作为结果
• 到达临界值时（左边等于右边），如果临界值小于查找目标值，会用左边加一去下一次查找。此时左边标记减一对应的值是小于目标值的，如果要给数组插入目标值会插入在这个值的后一个位置上，所以返回左边标记恰好是这个值的后一个位置。

public class Dichotomy {
    public static void main(String[] args) {
        int i = searchInsert(new int[]{1, 3, 5, 6}, 2);
        System.out.println(i);
    }

    public static int searchInsert(int[] nums, int target) {
        if (nums == null) {
            return 0;
        }
        return recursion(nums, target, 0, nums.length - 1);
    }

    private static int recursion(int[] nums,int target, int left, int right) {
        if (left > right) {
            return left ;
        }

        int index = (left + right + 1) / 2;
        if (nums[index] == target) {
            return index;
        }
        if (nums[index] > target) {
            return recursion(nums, target, left, index - 1);
        } else {
            return recursion(nums, target, index + 1, right);
        }
    }
}

迭代方法

也是二分思路

移位运算符的优先级比"+"优先级低

使用减法防止加法超出int存储限制

public class Dichotomy {
    public static void main(String[] args) {
        int i = searchInsert(new int[]{1, 3, 5, 6}, 5);
        System.out.println(i);
    }

    public static int searchInsert(int[] nums, int target) {
        if (nums == null) {
            return 0;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int index = left + ((right - left) >> 1);
            if (nums[index] == target) {
                return index;
            } else if (nums[index] > target) {
                right = index - 1;
            } else {
                left = index + 1;
            }
        }
        return left;
    }
}

---

题目来源作者：LeetCode 链接：https://leetcode.cn/leetbook/read/array-and-string/cxqdh/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。