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]
總結
到此這篇關於python二分法查找的文章就介紹到這瞭,更多相關python二分法查找內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- C++實現LeetCode(33.在旋轉有序數組中搜索)
- C++實現LeetCode(34.在有序數組中查找元素的第一個和最後一個位置)
- Python 二分查找之bisect庫的使用詳解
- go語言的四數相加等於指定數算法
- Java算法真題詳解運用單調棧