Python算法题集_搜索旋转排序数组
- 题33：搜索旋转排序数组
- 1. 示例说明
- 2. 题目解析
- - 题意分解
- - 优化思路
- - 测量工具
- 3. 代码展开
- 1) 标准求解【二分法+区间判断】
- 2) 改进版一【二分找分界+标准二分法】
- 3) 改进版二【递归实现二分法】
- 4. 最优算法
- 5. 相关资源
本文为Python算法题集之一的代码示例
题33：搜索旋转排序数组
1. 示例说明
-
整数数组
nums按升序排列，数组中的值 互不相同 。在传递给函数之前，
nums在预先未知的某个下标k（0 <= k < nums.length）上进行了 旋转，使数组变为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如，[0,1,2,4,5,6,7]在下标3处经旋转后可能变为[4,5,6,7,0,1,2]。给你 旋转后 的数组
nums和一个整数target，如果nums中存在这个目标值target，则返回它的下标，否则返回-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示例 3：
输入：nums = [1], target = 0 输出：-1提示：
1 <= nums.length <= 5000-104 <= nums[i] <= 104nums中的每个值都 独一无二- 题目数据保证
nums在预先未知的某个下标上进行了旋转 -104 <= target <= 104
2. 题目解析
- 题意分解
- 本题是将已排序列表旋转一次后，从中查找目标数值
- 最快方式就是二分法，原理是每次二分后检查左右边界，以[4,5,6,7,0,1,2]为例，左区间和右区间中，左边界小于等于target或者右边界大于等于target则target就在这个区间中
- 优化思路
-
通常优化：减少循环层次
-
通常优化：增加分支，减少计算集
-
通常优化：采用内置算法来提升计算速度
-
分析题目特点，分析最优解
-
老实说，二分法速度太快，评估速度性能优点难，标准算法就是题意分解解法
-
可以先找旋转的位置，就是原本nums[0]的位置，然后判断target在哪个区间后用标准二分法求解
-
可以考虑用递归法来实现二分法
-
- 测量工具
- 本地化测试说明：LeetCode网站测试运行时数据波动很大【可把页面视为功能测试】，因此需要本地化测试解决数据波动问题
CheckFuncPerf（本地化函数用时和内存占用测试模块）已上传到CSDN，地址：Python算法题集_检测函数用时和内存占用的模块- 本题本地化超时测试用例自己生成，详见章节【最优算法】，代码文件包含在【相关资源】中
3. 代码展开
1) 标准求解【二分法+区间判断】
二分法，查询区间左右边界和target
页面功能测试，性能一般，超过74%
import CheckFuncPerf as cfp
class Solution:
def search_base(self, nums, target):
ileft = 0
iright = len(nums)
while ileft < iright:
imid = ileft + ((iright - ileft) // 2)
if nums[imid] == target:
return imid
if nums[ileft] < nums[imid]:
if nums[ileft] <= target and target < nums[imid]:
iright = imid
else:
ileft = imid + 1
else:
if nums[imid] < target and target <= nums[iright - 1]:
ileft = imid + 1
else:
iright = imid
return -1
aSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.searchRange_base, nums, itarget)
print(result['msg'], '执行结果 = {}'.format(result['result']))
# 运行结果
函数 search_base 的运行时间为 0.00 ms；内存使用量为 136.00 KB 执行结果 = 86666667
2) 改进版一【二分找分界+标准二分法】
先用二分法查询原始nums[0]的下标，然后用标准二分法在有序数值中查找target
页面功能测试，惨不忍睹，超过14%
import CheckFuncPerf as cfp
class Solution:
def search_ext1(self, nums, target):
if len(nums) == 1:
if nums[0] == target:
return 0
else:
return -1
def base_search(nums, ileft, iright, itarget):
while ileft <= iright:
imid = ileft + (iright - ileft) // 2
if nums[imid] < itarget:
ileft = imid + 1
elif nums[imid] > itarget:
iright = imid - 1
else:
return imid
return -1
pos_div = 0
ileft, iright = 0, len(nums) - 1
while ileft <= iright:
imid = ileft + (iright - ileft) // 2
if imid > 0 and nums[imid] < nums[imid - 1]:
pos_div = imid
break
if nums[ileft] <= nums[imid] and nums[imid] > nums[iright]: # right is disordered
ileft = imid + 1
else:
iright = imid - 1
pos_div = ileft
if nums[len(nums) - 1] >= target >= nums[pos_div]:
return base_search(nums, pos_div, len(nums) - 1, target)
else:
return base_search(nums, 0, pos_div - 1, target)
aSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.search_ext1, nums, itarget)
print(result['msg'], '执行结果 = {}'.format(result['result']))
# 运行结果
函数 search_ext1 的运行时间为 0.00 ms；内存使用量为 4.00 KB 执行结果 = 86666667
3) 改进版二【递归实现二分法】
使用递归函数来实现二分法，另类做法
页面功能测试，性能一般，超过81%
import CheckFuncPerf as cfp
class Solution:
def search_ext2(self, nums, target):
def find_target(listnums, ileft, iright, itarget):
mid = (ileft + iright) // 2
if ileft > iright:
return -1
if ileft + 1 >= iright:
if listnums[ileft] == itarget:
return ileft
elif listnums[iright] == itarget:
return iright
else:
return -1
if listnums[ileft] < listnums[mid]:
if itarget >= listnums[ileft] and itarget <= listnums[mid]:
result = find_target(listnums, ileft, mid, itarget)
else:
result = find_target(listnums, mid + 1, iright, itarget)
else:
if itarget >= listnums[mid] and itarget <= listnums[iright]:
result = find_target(listnums, mid, iright, itarget)
else:
result = find_target(listnums, ileft, max(mid - 1, 0), itarget)
return result
return find_target(nums, 0, len(nums) - 1, target)
aSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.search_ext1, nums, itarget)
print(result['msg'], '执行结果 = {}'.format(result['result']))
# 运行结果
函数 search_ext1 的运行时间为 0.00 ms；内存使用量为 4.00 KB 执行结果 = 86666667
4. 最优算法
根据本地日志分析，本题怎么玩，只要是二分法，指标都差不多
import random
ilen, istart = 10000, 0
nums = [0 for x in range(ilen)]
for iIdx in range(ilen):
istart += random.randint(1, 3)
nums[iIdx] = istart
ipos, itarget = ilen//3, nums[ilen // 5]
checknums = nums[ipos:]
checknums.extend(nums[:ipos])
aSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.search_base, checknums, itarget)
print(result['msg'], '执行结果 = {}'.format(result['result']))
result = cfp.getTimeMemoryStr(aSolution.search_ext1, checknums, itarget)
print(result['msg'], '执行结果 = {}'.format(result['result']))
result = cfp.getTimeMemoryStr(aSolution.search_ext2, checknums, itarget)
print(result['msg'], '执行结果 = {}'.format(result['result']))
# 算法本地速度实测比较
函数 search_base 的运行时间为 0.00 ms；内存使用量为 136.00 KB 执行结果 = 86666667
函数 search_ext1 的运行时间为 0.00 ms；内存使用量为 4.00 KB 执行结果 = 86666667
函数 search_ext2 的运行时间为 0.00 ms；内存使用量为 84.00 KB 执行结果 = 86666667
5. 相关资源
本文代码已上传到CSDN，地址：Python算法题源代码_LeetCode(力扣)_搜索旋转排序数组
一日练，一日功，一日不练十日空
may the odds be ever in your favor ~
