题目
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜寻 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
输出: nums = [-1,0,3,5,9,12], target = 9输入: 4解释: 9 呈现在 nums 中并且下标为 4暴力枚举
for循环遍历数组元素，挨个判断。工夫复杂度O(n)
def search(nums, target) -> int: for i,num in enumerate(nums): if num == target: return i return -1二分法
二分法，实用于这种有序数组的查找。
二分法的思维，就是每次取两头的值与target比拟，而后放大范畴再取两头的值...：
- 如果两头值<target，就膨胀left
- 如果两头值>target，就膨胀right
如果两头值=target，须要分状况探讨
- 如果数组是[1,2,3,4]这种有序且不反复，就间接找到了
- 如果数组是其余状况，比方有反复，局部有序，局部有序且有反复，就须要思考左右边界，因为数组中可能有多个等于target的数，须要找最左侧的或是最右侧的
二分法工夫复杂度O(logn)，n/2^k=1，k=logn
规范二分，数组有序无反复元素
[1,2,3,4,5]，数组有序且无反复元素
while循环实现
def search(nums, target) -> int: left,right = 0, len(nums)-1 while left <= right: mid = (left+right)//2 if nums[mid]==target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1递归实现
def search(nums,target) -> int: def searchInternally(nums,target,left,right): if left<=right: mid = (left+right)//2 if nums[mid]==target: return mid elif nums[mid]<target: return searchInternally(nums,target,mid+1,right) else: return searchInternally(nums,target,left,mid-1) else: return -1 return searchInternally(nums,target,0,len(nums)-1)思考边界
数组有反复元素：[1,2,2,2,3]
数组局部有序：[4,5,6,1,2,3]
# 查找左边界def search(nums,target): left,right = 0, len(nums)-1 while left<right: mid = (left+right)//2 # 因为有反复元素，并且寻找左边界，所以当匹配到target后，膨胀right，持续向左查找 if nums[mid]==target: right = mid if nums[mid] > target: right = mid -1 if nums[mid] < target: left = mid +1 return left if nums[left]==target else -1# 查找右边界def search(nums, target): left, right = 0, len(nums) - 1 while left < right: # 因为查找右边界，mid本来的计算是向下取整，导致靠左，所以+1靠右 mid = (left + right) // 2 + 1 if nums[mid] == target: # 膨胀left，持续向右查找 left = mid if nums[mid] > target: right = mid - 1 if nums[mid] < target: left = mid + 1 return right if nums[right] == target else -1数组局部有序，且反复：[1,2,2,3,1,2,2,3]
# 查找左边界def search(nums, target): left,right = 0, len(nums)-1 while left < right: mid = (left+right)//2 if nums[mid]==target: right = mid if nums[mid]>target: # 因为数组局部有序且反复，mid大于target时， # 有可能mid左侧没有目标值，在右侧有，因而膨胀right时只能一点一点膨胀 right = right - 1 if nums[mid]<target: left = mid + 1 return left if nums[left]==target else -1