[leetcode]35.搜索插入位置

题目

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

你可以假设数组中无重复元素。

示例 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) {
    return binSearch(0,nums.length-1,target,nums);
}

public int binSearch(int left, int right, int x, int[] nums) {
    if (left > right) return left;
    int mid = (left + right) / 2;
    if (x < nums[mid]) return binSearch(left, mid - 1, x, nums);
    if (x > nums[mid]) return binSearch(mid + 1, right, x, nums);
    if (x == nums[mid]) return mid;
    return -1;
}

这里是采用传统的递归来写二分，但其实这里可以不用，直接一个while循环就行

public int searchInsert(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        // 防止溢出
        int mid = left + ((right - left) >> 1);
        if (target == nums[mid]) {
            return mid;
        } else if (target < nums[mid]) {
            right = mid - 1;
        } else if (target > nums[mid]) {
            left = mid + 1;
        }
    }
    return left;
}