二分查找，给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。或者将target插入数组中返回插入位置下标。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4
# 二分查找
def nums_search(lst, val):
"""
:param lst:
:param val:
:return:
"""
left = 0
right = len(lst) - 1
while left <= right:
mid = (left + right) // 2
if lst[mid] == val:
return mid
elif lst[mid] > val: # 待查找的值在mid左侧
right = mid - 1
else: # 待查找的值在mid右侧
left = mid + 1
# 找不到
else:
return None # 将-1改成left即返回插入位置下标
li = [-1, 0, 2, 3, 5, 6, 7, 8, 9]
# 查3
print('下标为：', nums_search(li, 3))
结果：
下标为： 3
面向对象：
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target: # 待查找的值在mid左侧
right = mid - 1
else: # 待查找的值在mid右侧
left = mid + 1
else:
return -1 # 将-1改成left即返回插入位置下标
运行最快的方式：
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
if target in nums:
return nums.index(target)
else:
nums.append(target)
nums.sort()
return nums.index(target)
