Python算法题集_搜索旋转排序数组

本文为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
  1
  2

  示例 2：

  输入：nums = [4,5,6,7,0,1,2], target = 3
  输出：-1
  1
  2

  示例 3：

  输入：nums = [1], target = 0
  输出：-1
  1
  2

  提示：

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -104 <= target <= 104

---

2. 题目解析

- 题意分解

1. 本题是将已排序列表旋转一次后，从中查找目标数值
2. 最快方式就是二分法，原理是每次二分后检查左右边界，以[4,5,6,7,0,1,2]为例，左区间和右区间中，左边界小于等于target或者右边界大于等于target则target就在这个区间中

- 优化思路

1. 通常优化：减少循环层次

2. 通常优化：增加分支，减少计算集

3. 通常优化：采用内置算法来提升计算速度

4. 分析题目特点，分析最优解

   1. 老实说，二分法速度太快，评估速度性能优点难，标准算法就是题意分解解法

   2. 可以先找旋转的位置，就是原本nums[0]的位置，然后判断target在哪个区间后用标准二分法求解

   3. 可以考虑用递归法来实现二分法

- 测量工具

• 本地化测试说明：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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

---

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

5. 相关资源

本文代码已上传到CSDN，地址：Python算法题源代码_LeetCode(力扣)_搜索旋转排序数组

一日练，一日功，一日不练十日空

may the odds be ever in your favor ~