二分查找实践
- 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)
