Python-搜索插入位置
题目
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置
请必须使用时间复杂度为 O(log n) 的算法
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
提示:
- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
- nums 为 无重复元素 的 升序 排列数组
- -104 <= target <= 104
题解
思路
暴力遍历
- 如果数组中的值大于或者等于 target，直接 return
- 如果全部遍历完证明 target 是最大的数，直接插入末尾
缺点：数值较多时，没有那么高效，因此可以引入二分查找
二分查找
- left=0，right=nums.length,取mid为中间值
- 如果nums[mid]==target,返回mid值，循环终止
- 如果nums[mid]>target,就说明从mid到right之间的值都是“无用的”需要挪动right，而我们能知道的接近的一个无用的值是mid，因此right必须比mid还要小才行，也即是right=mid-1
- 同理，left=mid+1
- 一直循环，除非找到mid值或者发现target根本不在目标中，也就是已经完全循环了一遍(left>right),这时候的right的值就是最接近target但又大于target的值（可以拿0来举例自己画一遍过程），因此 return right+1
代码
暴力遍历
class Solution:def searchInsert(self, nums: List[int], target: int) -> int:for i in range(len(nums)):if nums[i] >= target:return ireturn len(nums)
二分法
class Solution:def searchInsert(self, nums: List[int], target: int) -> int:if len(nums) < 1: return 0left = 0right = len(nums) - 1while(left <= right):mid = left + (right - left) // 2if nums[mid] == target:return midelif nums[mid] > target:right = mid - 1else:left = mid + 1return right + 1
