Python每日一练-----搜索插入的位置

（day31）

目录

题目：

题目分析：

解题思路：

代码实现

代码注释

题目：

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

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

⭐示例 1：

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

输出: 2

解释说明：目标数所在索引为2

⭐示例 2:

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

输出: 1

解释说明：数组（列表）中没有目标数，将2插入到1和3当中，这是2的索引为1

⭐示例 3：

输入: nums = [1,3,5,6], target = 7

输出: 4

题目分析：

题目要求的是返回目标数的索引（也称下标），如果数组列表nums中没有目标数，那么就需要将其插入到列表中再返回目标数1的索引。题目还要求必须使用时间复杂度为O（logn）的方法来做。（不清楚时间空间复杂度的小伙伴可看：一个小故事带你了解大O表示法

看到O（logn）我们第一时间想到的应该是二分法。

解题思路：

按照题目解题时间复杂度的限制，我们使用二分法解题。二分法的精髓，每次解决一半的问题。题目已经将列表nums排序好了，那么我们就可以直接将从首尾开始进行二分。

我们在首尾放置指针，并判断列表nums“中间数”（中间数就是列表最中间的数，如果列表长度为偶数取最中间两个数之一），与目标值target的关系。

✨如果目标值target 正好等于列表的中间数

那么我们返回中间数的索引即可

✨如果目标值target  > 列表的中间数

那么我们将左（首）指针右移到中间数的右一个位置。

为什么要移到右一个位置？

因为我们已经判断了中间数不等于目标数target，所以我们直接将左指针移到中间数的右一个位置，这样能尽可能缩小排查范围。

✨如果目标值target <  列表的中间数

同理，我们将右（尾）指针左移到中间数的左一个位置。

我们将着三步操作放入到循环中进行，由于左右指针相遇时说明列表以遍历完成，所以循环进行的条件可以设置为左指针 <= 右指针

那么如和实现题目所说的，当目标值不在列表中是需要将目标值加入到列表并判断其索引？

我们考虑到，如果目标数不在列表当中，遍历完列表也不会出现中间数等于目标值的情况。由循环结束条件我们知道，循环结束时目标值是位于右指针和左指针之间，只是不在列表中无法找到目标值下标。但我们并不需要将目标值真正加入到列表中。因为目标值就在右指针和左指针之间所以我们只需返回右指针的索引+1即可。此时右指针的索引+1即为目标值的索引

代码实现

def searchInsert(nums, target):
    left = 0
    right = len(nums) - 1
    
    while left <= right:
        middle = (left + right) // 2

        if nums[middle] < target:
            left = middle + 1
        elif nums[middle] > target:
            right = middle - 1
        else:
            return middle
    return right + 1

代码注释

def searchInsert(nums, target):
    left = 0  # 初始化左指针
    right = len(nums) - 1  # 初始化右指针

    while left <= right:
        middle = (left + right) // 2  # 中间数的索引
        
        # 依据判断分析移动指针
        if nums[middle] < target: 
            left = middle + 1
        elif nums[middle] > target:
            right = middle - 1
        else:
            return middle
    return right + 1  # 循环结束还未找到目标数索引，返回右指针+1

这里说明右指针初始化的依据，右指针右很多人喜欢初始化未right = len（nums），这并没有对错之分。这二者的区别是

当列表nums长度为偶数时

初始化右指针为right = len（nums）则取最中间的两个数时取靠右的那个

初始化右指针为right = len（nums）则取最中间的两个数时取靠左的那个

----------------------------------------------------

如nums = [1, 2, 3, 4]

前者（middle为中间数索引）

middle = (left + right) // 2 = 2

后者

middle = (left + right) // 2 = 1

---------------------------------------------------

还有就是为什么返回的是right+1。

因为当right=left时while循环还会执行，且我们初始化right=len（nums）- 1，所以当列表长度为偶数时我们都是取靠左的中间数，本来目标值是在左右指针之间，现在循环结束左右指针重合到中间数的索引处，所以返回right+1.其实返回left也是一样的结果。

今天就到这，明天见。

❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄end❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄