LeetCode 35. 搜索插入位置（易）

减治：通过不断排除非目标元素，在循环结束之后，最后剩下的那个元素，必然是我们想要的目标元素。减治思想特点，将二分法查找区间，从以前的[left, mid]、mid、[mid, right] 三个部分改成两个区间。

题目

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

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

示例

示例 1:

1
2
输入: [1,3,5,6], 5
输出: 2

示例 2: 

1
2
输入: [1,3,5,6], 2
输出: 1
示例 3: 
1
2
输入: [1,3,5,6], 7
输出: 4
示例 4: 
1
2
输入: [1,3,5,6], 0
输出: 0

考察知识点

数组、二分查找

核心思想

基于普通二分查找

利用二分查找，找到了就直接返回，没找到，根据返回小标对应数组中的值和target的关系，做一些特判也可以返回确定应该插入的位置。

基于减治思想的二分查找

减治：通过不断排除非目标元素，在循环结束之后，最后剩下的那个元素，必然是我们想要的目标元素。
减治思想特点，将二分法查找区间，从以前的[left, mid]、mid、[mid, right] 三个部分改成两个区间。
1.png

减治思想代码步骤
2.png

区间划分代码写法
937bfc80f71eb782a2ad2aefd1ca449c2d5ccc100ee5317ee9e1556c1b01d022-0035-5.png

当边界收缩行为是left = mid时，出现死循环的原因。注意 left = middle-1，right = middle 的情况下，循环条件是 left < right ，此时是不会出现死循环的。不能写成 left = middle-1，right = middle+1，循环条件为 left <= right，这样会出现死循环。
bb5c606d21382ab119db271f15ec2c8a4183925db67843ab776400e17ca6ab7e-0035-6.png

思路：（如果二分查找一开始写不出来，可以尝试先写暴力法，分析清楚细节）在有序数组中查找插入元素的位置，显然可以使用二分查找。这篇题解提供的思路是“减治思想（排除法）”，即在循环的过程中，不断排除不需要的解，最后剩下的那个元素就一定是我们想要的。

  • 首先，插入位置有可能在数组的末尾（题目中的示例 3），需要单独判断；
  • 其次，如果待插入元素比最后一个元素严格小，并且在这个数组中有和插入元素一样的元素，返回任意一个位置即可；
  • 否则，插入的位置应该是严格大于 target 的第 1 个元素的位置。（这里是关键） 因此，严格小于 target 的元素一定不是解，根据这个思路，可以写出如下代码。

关于二分查找问题的总结
6.png

参考链接

二分查找法优秀题解

Python版本

基于普通二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def searchInsert(self, nums: list, target: int) -> int:
        def search(left, right):
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] == target:
                    return mid
                elif nums[mid] > target:  # 去左区间找 减小right
                    right = mid - 1
                else:  # 否则去右区间找 增大left
                    left = mid + 1

            # return mid
            return right  # 为了解决 nums = [1,3]，target = 2，answer = 0 的情况，不返回mid，而是返回right，并在外面做判断，如果right=-1，说明没能找到，且target小于所有数字，所有应该插入在0这个位置。
        
        length = len(nums)
        _index = search(0, length - 1)
        if nums[_index] != target:
            if _index == -1:
                return 0
            elif nums[_index] < target:
                return _index + 1
            else:
                return _index - 1 if _index != 0 else 0
        else:
            return _index

print("leet code accept!!!")
Input = [[1,3,5,6], [1,3,5,6], [1,3,5,6], [1,3]]
Input1 = [5, 2, 0, 2]
Answer = [2, 1, 0, 1]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        result = solution.searchInsert(Input[i], Input1[i])
        print(result==Answer[i])

时间复杂度，就一个二分查找 \(O(logN)\) 。
空间复杂度为，只需要存储几个变量的额外空间 \(O(1)\)。
执行用时 :32 ms, 在所有 Python3 提交中击败了98.83%的用户
内存消耗 :14 MB, 在所有 Python3 提交中击败了30.81%的用户

基于减治思想的二分查找

推荐此方法，更简洁！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from typing import List
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        size = len(nums)
        if size == 0:
            return 0

        # 特判
        if nums[size - 1] < target:
            return size

        left = 0
        right = size - 1
		# 插入的位置应该是严格大于 target 的第 1 个元素的位置。（这里是关键）
        while left < right:
            mid = left + (right - left) // 2  # 防止left、right太大溢出了。
            # 严格小于 target 的元素一定不是解
            if nums[mid] < target:
                # 下一轮搜索区间是 [mid + 1, right]，小于的target的这部分就不要了，去右区间找，left调大且不用包含mid。
                left = mid + 1
            else:  # 否则，下一轮的搜索区间就是[left, mid]，去左区间，因为只有在这个区间内才能找到严格大于target的第 1 个元素。
                right = mid
        return left

时间复杂度，就一个二分查找 \(O(logN)\) 。
空间复杂度为，只需要存储几个变量的额外空间 \(O(1)\)。
执行用时 :40 ms, 在所有 Python3 提交中击败了95.76%的用户
内存消耗 :14 MB, 在所有 Python3 提交中击败了31.52%的用户

有效语法糖

1、利用typing模块进行参数检测

1
2
3
4
from typing import List
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
    	pass