快捷導(dǎo)航

python二分法查找實(shí)例代碼

更新時(shí)間：2021年11月21日 16:11:52 作者：欒沫

二分算法是一種效率比較高的查找算法,其輸入的是一個(gè)有序的元素列表,如果查找元素包含在列表中,二分查找返回其位置,否則返回NONE,下面這篇文章主要給大家介紹了關(guān)于python二分法查找的相關(guān)資料,需要的朋友可以參考下

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

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

題目一：給定一個(gè) n 個(gè)元素有序的（升序）整型數(shù)組 nums 和一個(gè)目標(biāo)值 target? ，寫(xiě)一個(gè)函數(shù)搜索 nums 中的 target，如果目標(biāo)值存在返回下標(biāo)，否則返回 -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

題目二：在一個(gè)嚴(yán)格遞減的數(shù)組中，找到第二個(gè)比目標(biāo)值target大的數(shù)的下標(biāo)。若不存在，則返回-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ù)應(yīng)該以長(zhǎng)度為 2 的整數(shù)數(shù)組的形式返回這兩個(gè)數(shù)的下標(biāo)值。numbers 的下標(biāo) 從 1 開(kāi)始計(jì)數(shù) ，所以答案數(shù)組應(yīng)當(dāng)滿足 1 <= answer[0] < answer[1] <= numbers.length 。你可以假設(shè)每個(gè)輸入只對(duì)應(yīng)唯一的答案，而且你不可以重復(fù)使用相同的元素。

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]

總結(jié)

到此這篇關(guān)于python二分法查找的文章就介紹到這了,更多相關(guān)python二分法查找內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: