You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
|
|
|
|
|
'''
|
|
|
|
|
|
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。
|
|
|
|
|
|
示例 1：输入：[1,3,5,6], 5 输出：2
|
|
|
|
|
|
示例 2：输入：[1,3,5,6], 2 输出：1
|
|
|
|
|
|
示例 3：输入：[1,3,5,6], 7 输出：4
|
|
|
|
|
|
示例 4：输入：[1,3,5,6], 0 输出：0
|
|
|
|
|
|
'''
|
|
|
|
|
|
|
|
|
|
|
|
class Solution(object):
|
|
|
|
|
|
def searchInsert(self, nums, target): # 二分法
|
|
|
|
|
|
"""
|
|
|
|
|
|
:type nums: List[int]
|
|
|
|
|
|
:type target: int
|
|
|
|
|
|
:rtype: int
|
|
|
|
|
|
"""
|
|
|
|
|
|
lo = 0
|
|
|
|
|
|
hi = len(nums)
|
|
|
|
|
|
while lo < hi:
|
|
|
|
|
|
mid = lo + (hi - lo)/2 # 可以用右移1位代替，mid=(left+right)>>1，位移运算的效率更高
|
|
|
|
|
|
if nums[mid] > target:
|
|
|
|
|
|
hi = mid
|
|
|
|
|
|
elif nums[mid] < target:
|
|
|
|
|
|
lo = mid + 1
|
|
|
|
|
|
else:
|
|
|
|
|
|
return mid
|
|
|
|
|
|
return lo
|
