题目描述:给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
具体思路: 考虑二分法。
方法一:直接调用函数
python中的bisect库提供二分查找和插入。其中bisect_left()时,插入点在已存在元素之前;bisect_right时,插入点在已存在元素之后。具体用法见python官方文档。https://docs.python.org/zh-cn/3.8/library/bisect.html
1 class Solution: 2 def searchInsert(self, nums: List[int], target: int) -> int: 3 import bisect 4 return bisect.bisect_left(nums,target)
方法二:传统二分查找代码
初始化左指针和右指针,left=0,right=len(nums)-1。当left≤right时,令mid = (left+right)//2,进行如下判断:
- 当nums[mid] == target时,return mid
- 当nums[mid] < target时,left = mid+1
- 当nums[mid] > target时,right = mid-1
通过提前考虑极限情况来优化代码。如果要寻找的值小于最小值或大于最大值,则插入到列表的首部或尾部。
1 class Solution: 2 def searchInsert(self, nums: List[int], target: int) -> int: 3 if target > nums[-1]: 4 return len(nums) 5 if target == nums[-1]: 6 return len(nums)-1 7 if target <= nums[0]: 8 return 0 9 left,right = 0,len(nums)-1 10 while(left <= right): 11 mid = (left+right)//2 12 if target == nums[mid]: 13 return mid 14 if target < nums[mid]: 15 right = mid-1 16 else: 17 left = mid+1 18 return left