二分查找實踐
- 2019 年 10 月 5 日
- 筆記
二分查找實踐
0.說在前面1.二分查找實現2.搜索旋轉排序數組2.1 問題2.2 思想3.非遞歸實現4.遞歸實現5.作者的話
0.說在前面
本周還差一次leetcode刷題，今日補上，今天刷的題為搜索旋轉排序數組，實現方式採用遞歸與非遞歸實現！下面一起來實踐吧！
1.二分查找實現
二分查找概念不闡述了，這裡直接來做實現，為後面的題目做準備！
class BS: def search(self,nums,target): return self.bsearch(nums,0,len(nums)-1,target) def bsearch(self,nums,low,high,target): while(low<=high): mid = (low+high)//2 if nums[mid] == target: return mid elif nums[mid] < target: low=mid+1 elif nums[mid] > target: high=mid-1 return None nums = [9,5,7,0,1,2,3,12] target = 0 bs = BS() print(bs.search(nums,target))
2.搜索旋轉排序數組
2.1 問題
假設按照升序排序的數組在預先未知的某個點上進行了旋轉。
( 例如，數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。
搜索一個給定的目標值，如果數組中存在這個目標值，則返回它的索引，否則返回 -1 。
你可以假設數組中不存在重複的元素。
你的演算法時間複雜度必須是 O(log n) 級別。
示例 1:
輸入: nums = [4,5,6,7,0,1,2], target = 0 輸出: 4
示例 2:
輸入: nums = [4,5,6,7,0,1,2], target = 3 輸出: -1
2.2 思想
如果中間值大於最左邊值，表示中間值與左邊在一個遞增序列中，此時只需要判斷一下target是否在左邊與中間這個區間，這就變成了一個標準的遞增排序數組查找！
如果中間值小於左邊值，表示中間值肯定在右邊的一個遞增序列中，此時只需要判斷一下target是不是在中間與右邊這個區間，這就變成了一個標準的遞增排序數組查找！
3.非遞歸實現
思想上面闡述了，下面來實現！
def search(self, nums, target): low = 0 high = len(nums)-1 mid = (low + high)//2 while low<=high: if nums[mid] == target: return mid elif nums[mid]>=nums[low]: if nums[mid] >= target and target >= nums[low]: high = mid - 1 else: low = mid + 1 elif nums[mid]<nums[low]: if nums[mid] <= target and target <= nums[high]: low = mid + 1 else: high = mid - 1 mid = (low + high)//2 return -1
4.遞歸實現
下面設置十萬次，原因是因為python遞歸會有限制，所以設置多一點，就不會出問題！對比這兩段程式碼，核心基本是一致的！
def search(self, nums, target): import sys sys.setrecursionlimit(100000) # 這裡設置為十萬 return self.zheban(nums, target, 0, len(nums) - 1) def zheban(self, nums, target, low, high): if high < low: return -1 mid = (low + high) // 2 if nums[mid] == target: return mid if nums[mid] >= nums[low]: if nums[mid] >= target and target >= nums[low]: return self.zheban(nums, target, low, mid - 1) else: return self.zheban(nums, target, mid + 1, high) else: if nums[mid] <= target and target <= nums[high]: return self.zheban(nums, target, mid + 1, high) else: return self.zheban(nums, target, low, mid - 1)
