[数据结构与算法]python二分法查找

二分查找有个很重要的特点，就是不会查找数列的全部元素，而查找的数据量其实正好符合元素的对数，正常情况下每次查找的元素都在一半一半地减少。所以二分查找的时间复杂度为 O(log2n) 是毫无疑问的。当然，最好的情况是只查找一次就能找到，但是在最坏和一般情况下的确要比顺序查找好了很多。

题目一：给定一个?n?个元素有序的（升序）整型数组?nums?和一个目标值?target??，写一个函数搜索?nums?中的?target，如果目标值存在返回下标，否则返回?-1。

class Solution:
    def search(self,nums:List[int],target:int)->int:
        left=0
        right=len(nums)-1
        while(left<=right):
            mid=(left+right)//2
            if nums[mid]==target:
               return mid
            if nums[mid]<target:
                left=mid+1
            else:
                right=mid-1
        return -1

题目二：在一个严格递减的数组中，找到第二个比目标值target大的数的下标。若不存在，则返回-1。?

class Solution:
    def search(self,nums:List[int],target:int)->int:
        left=0
        right=len(nums)-1
        while(left<=right):
            mid=(left+right)//2
            if nums[mid]==target:
               return mid
            if nums[mid]>target:
                left=mid+1
            else:
                right=mid-1
        return -1

题目三：函数应该以长度为?2?的整数数组的形式返回这两个数的下标值。numbers?的下标?从 1 开始计数?，所以答案数组应当满足?1 <= answer[0] < answer[1] <= numbers.length?。你可以假设每个输入?只对应唯一的答案?，而且你?不可以?重复使用相同的元素。

class Solution:
     def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)-1):
            left=i
            right=len(numbers) - 1
            while(left<=right):
                mid=(left+right)//2
                if numbers[mid]+numbers[i]==target:
                    return [i+1,mid+1]
                elif numbers[mid]+numbers[i]<target:
                    left=mid+1
                else:
                    right = mid-1
            return [-1,-1]

?