题目

力扣题目链接

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

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

示例 1:

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

示例 2:

  1. 输入: nums = [1,3,5,6], target = 0
  2. 输出: 0

提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 为无重复元素的升序排列数组
  • -10^4 <= target <= 10^4

思路

做这道题之前，先把 704. 二分查找 这道题做了。

这道题目，要在数组中插入目标值，无非是这四种情况：

  • 目标值在数组所有元素之前
  • 目标值等于数组中某一个元素
  • 目标值插入数组中的位置
  • 目标值在数组所有元素之后

如图所示：
image.png

这四种情况确认清楚了，就可以尝试解题了。

大家注意这道题目的前提是数组是有序数组，这也是使用二分查找的基础条件。

以后大家只要看到面试题里给出的数组是有序数组，都可以想一想是否可以使用二分法。

同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下表可能不是唯一的。

大体讲解一下二分法的思路，这里来举一个例子，例如在这个数组中，使用二分法寻找元素为5的位置，并返回其下标。
image.png

二分查找涉及的很多的边界条件，逻辑比较简单，就是写不好。

相信很多同学对二分查找法中边界条件处理不好。

例如到底是 while(left < right) 还是 while(left <= right)，到底是 right = middle 呢，还是要 right = middle - 1 呢？

相信你做过 704. 二分查找 这道题之后就不会有这样的疑问了。

在二分查找的过程中，保持对区间的定义。这样二分查找写起来就不容易迷糊了。

答案

Java

以这道题目来举例，以下的代码中定义 target 是在一个在左闭右闭的区间里，也就是 [left, right] （这个很重要）。
区间的定义直接决定了二分法的代码如何去写，大家要仔细看注释，思考为什么要写while(left <= right)， 为什么要写right = middle - 1。

  1. class Solution {
  2.     public int searchInsert(int[] nums, int target) {
  3.         // 特例处理
  4.         if (target < nums[0]) {
  5.             // 目标值在数组所有元素之前
  6.             return 0;
  7.         } else if (target > nums[nums.length - 1]) {
  8.             // 目标值在数组所有元素之后
  9.             return nums.length;
  10.         }
  12.         int left = 0, right = nums.length - 1;
  13.         // 当 left==right ，区间 [left, right] 依然有效，所以用 <=
  14.         while (left <= right) {
  15.             // 防止溢出 等同于(left + right)/2
  16.             int mid = left + ((right - left) >> 1);
  17.             System.out.println(mid);
  19.             if (nums[mid] > target) {
  20.                 // target 在左区间，所以[left, middle - 1]
  21.                 right = mid - 1;
  22.             } else if (nums[mid] < target) {
  23.                 // target 在右区间，所以[middle + 1, right]
  24.                 left = mid + 1;
  25.             } else {
  26.                 // nums[middle] == target
  27.                 return mid;
  28.             }
  29.         }
  31.         // 分别处理如下四种情况
  32.         // 目标值在数组所有元素之前  [0, -1]
  33.         // 目标值等于数组中某一个元素  return middle;
  34.         // 目标值插入数组中的位置 [left, right]，return  right + 1
  35.         // 目标值在数组所有元素之后的情况 [left, right]， return right + 1
  36.         return right + 1;
  37.     }
  38. }

REF

https://leetcode-cn.com/problems/search-insert-position/
https://programmercarl.com/0035.搜索插入位置.html