题目

给定一个 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