python二分法查找怎么使用

這篇文章主要講解了“python二分法查找怎么使用”，文中的講解內(nèi)容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“python二分法查找怎么使用”吧！

對于要搜索的元素越多，二分查找速度比簡單查找快的更多 這是二分查找算法的優(yōu)點，但二分算法也有缺點，二分算法只針對有序的列表，這樣插入和刪除就會很困難，因此，折半查找方法只適合不經(jīng)常變動的有序列表

 二分查找有個很重要的特點，就是不會查找數(shù)列的全部元素，而查找的數(shù)據(jù)量其實正好符合元素的對數(shù)，正常情況下每次查找的元素都在一半一半地減少。所以二分查找的時間復雜度為 O(log2n) 是毫無疑問的。當然，最好的情況是只查找一次就能找到，但是在最壞和一般情況下的確要比順序查找好了很多。

題目一：給定一個 n 個元素有序的（升序）整型數(shù)組 nums 和一個目標值 target  ，寫一個函數(shù)搜索 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

題目二：在一個嚴格遞減的數(shù)組中，找到第二個比目標值target大的數(shù)的下標。若不存在，則返回-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

題目三：函數(shù)應該以長度為 2 的整數(shù)數(shù)組的形式返回這兩個數(shù)的下標值。numbers 的下標 從 1 開始計數(shù) ，所以答案數(shù)組應當滿足 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]

感謝各位的閱讀，以上就是“python二分法查找怎么使用”的內(nèi)容了，經(jīng)過本文的學習后，相信大家對python二分法查找怎么使用這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！