[LeetCode] 35. Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

Example 4:

Input: nums = [1,3,5,6], target = 0
Output: 0

Example 5:

Input: nums = [1], target = 0
Output: 0

Constraints:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums contains distinct values sorted in ascending order.
-104 <= target <= 104

搜索插入位置。

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二分法基础题。给一个数字和一个有序数组，如果这个数字在数组中存在，返回其坐标；否则返回它应该被插入的位置。

二分法不难想到，但是面试的重点是你如何能把二分法写对。我个人比较喜欢第一种实现方法。注意while循环的条件，比如我下面的代码，left <= right，你可以这样想，最后while跳出循环的时候，一定是left > right，所以在while循环的最后一步的时候，left == right。同时找到mid但是mid上的元素不满足条件的时候，为什么right = mid - 1（left = mid + 1）？那是因为mid位置上的元素一定不满足了，所以在确定新的边界的时候可以将mid去掉。

时间O(logn)

空间O(1)

JavaScript实现

 1 /**
 2  * @param {number[]} nums
 3  * @param {number} target
 4  * @return {number}
 5  */
 6 var searchInsert = function(nums, target) {
 7     let left = 0;
 8     let right = nums.length - 1;
 9     while (left <= right) {
10         let mid = Math.floor(left + (right - left) / 2);
11         if (nums[mid] === target) {
12             return mid;
13         } else if (nums[mid] > target) {
14             right = mid - 1;
15         } else {
16             left = mid + 1;
17         }
18     }
19     return left;
20 };

Java实现

 1 class Solution {
 2     public int searchInsert(int[] nums, int target) {
 3         int left = 0;
 4         // range is [left, right]
 5         int right = nums.length - 1;
 6         while (left <= right) {
 7             int mid = left + (right - left) / 2;
 8             if (nums[mid] == target) {
 9                 return mid;
10             } else if (nums[mid] > target) {
11                 right = mid - 1;
12             } else {
13                 left = mid + 1;
14             }
15         }
16         return left;
17     }
18 }

Java实现二，注意右边界的定义和mid是如何移动的

因为右边界 right = nums.length 在定义的时候就事实上已经越界了，下标最多是到 nums.length - 1 的。所以当 mid > target 的时候，right = mid，是为了确保 mid 也在被扫描的范围内。

时间空间复杂度同实现一

 1 class Solution {
 2     public int searchInsert(int[] nums, int target) {
 3         int left = 0;
 4         int right = nums.length;
 5         while (left < right) {
 6             int mid = left + (right - left) / 2;
 7             if (nums[mid] == target) {
 8                 return mid;
 9             } else if (nums[mid] > target) {
10                 right = mid;
11             } else {
12                 left = mid + 1;
13             }
14         }
15         return left;
16     }
17 }