python二分法查找實例代碼
發(fā)布日期：2021-12-09 00:24 | 文章來源：站長之家
對于要搜索的元素越多，二分查找速度比簡單查找快的更多 這是二分查找算法的優(yōu)點，但二分算法也有缺點，二分算法只針對有序的列表，這樣插入和刪除就會很困難，因此，折半查找方法只適合不經(jīng)常變動的有序列表
?二分查找有個很重要的特點，就是不會查找數(shù)列的全部元素，而查找的數(shù)據(jù)量其實正好符合元素的對數(shù)，正常情況下每次查找的元素都在一半一半地減少。所以二分查找的時間復(fù)雜度為 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ù)應(yīng)該以長度為 2 的整數(shù)數(shù)組的形式返回這兩個數(shù)的下標值。numbers 的下標 從 1 開始計數(shù) ，所以答案數(shù)組應(yīng)當滿足 1 <= answer[0] < answer[1] <= numbers.length 。你可以假設(shè)每個輸入 只對應(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)容請搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站！
版權(quán)聲明：本站文章來源標注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習參考，不代表本站立場，如有內(nèi)容涉嫌侵權(quán)，請聯(lián)系alex-e#qq.com處理。
相關(guān)文章
關(guān)注官方微信