作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
“搜索旋转排序数组”，这是一道中等难度的题目，主要考查对二分查找算法的理解和应用，特别是在处理包含旋转的有序数组时的变体情形。下面我们将详细讨论这个问题。
问题描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [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
二分查找-解题步骤
- 确定旋转点：
- 识别数组是如何被旋转的。可以通过比较数组首尾元素的大小来理解旋转的部分。
- 二分查找应用：
- 使用二分查找来确定目标值的位置。但由于数组被旋转，我们需要在标准二分查找的基础上进行修改。
- 调整二分查找条件：
- 在二分查找的每一步中，首先确定中间元素
mid。 - 确定
mid分割后的两部分哪一部分是完全排序的。 - 根据目标值
target的位置，决定是在有序部分进行标准的二分查找，还是在另一部分继续进行条件修改后的二分查找。
- 重复上述过程：
- 直到找到目标值或确定目标值不存在。
代码示例
class Solution: def search(self, nums: List[int], target: int) -> int: if not nums: return -1 left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 # 如果中间的数就是目标值，则直接返回索引 if nums[mid] == target: return mid # 确定哪一半是有序的 if nums[left] <= nums[mid]: # 如果左边是有序的 if nums[left] <= target < nums[mid]: right = mid - 1 # 目标在左侧 else: left = mid + 1 # 目标在右侧 else: # 右边是有序的 if nums[mid] < target <= nums[right]: left = mid + 1 # 目标在右侧 else: right = mid - 1 # 目标在左侧 # 如果没有找到目标值 return -1
代码解释
- 初始化指针：
left和right指针分别初始化为数组的开始和结束位置。 - 二分查找：
- 计算中间位置
mid。 - 检查
nums[mid]是否等于target，如果是，则直接返回mid。
- 判断有序段：
- 判断左半部分是否有序（即
nums[left]是否小于等于nums[mid]）。 - 如果左侧有序，检查
target是否位于左侧的范围内 (nums[left]到nums[mid])，如果是，则调整right指针。 - 如果左侧不有序，则右侧必有序，检查
target是否位于右侧的范围内 (nums[mid]到nums[right])，如果是，则调整left指针。
- 调整指针：根据上述逻辑，移动
left或right指针来缩小查找范围。 - 返回结果：如果循环结束还没找到
target，返回-1。
性能分析
- 时间复杂度：O(logn)，即使数组被旋转，二分查找仍能保持对数级的时间复杂度。
- 空间复杂度：O(1)，使用了常数空间以存储几个指针。
算法图解
假设数组为 [4, 5, 6, 7, 0, 1, 2]，目标值为 0。
Initial Array: Index: 0 1 2 3 4 5 6 Value: 4 5 6 7 0 1 2 | | left right -> <- Mid index calculation (3): | | | left mid right | Mid Value = 7 Step 1: Target not in [4,7], shift to right half | | left right -> <- 4 5 6 0 1 2 left right -> <- Mid index calculation (5): | | left mid right | Mid Value = 1 Step 2: Target in [0,1], continue in right half | | left right mid | Mid Value = 0 Step 3: Target found at index 4
算法优化
我们还可以从几个角度来考虑优化这个算法，主要是通过简化逻辑、减少计算步骤、和增强代码的鲁棒性和可读性。
优化方向
- 简化条件判断逻辑：原算法中包含多个条件判断来确定搜索的方向，这些判断有时可以合并或重新组织以简化逻辑。
- 避免不必要的比较：在判断有序部分时，可以通过更少的比较来实现。例如，可以先检查目标是否在当前中值的一侧，如果不是再确认另一侧是否有序。
- 提升可读性和维护性：通过提取复杂的判断逻辑为单独的函数，不仅可以使主函数更简洁，也方便未来的维护和修改。
- 使用迭代而非递归：虽然原方案已经是迭代，但强调迭代的好处是空间复杂度为 O(1)，相比递归方法的空间复杂度 O(logn) 有显著优势。
优化后的代码示例
class Solution: def search(self, nums: List[int], target: int) -> int: # 如果数组为空，则直接返回-1 if not nums: return -1 # 初始化左右指针 left, right = 0, len(nums) - 1 while left <= right: # 计算中间位置 mid = (left + right) // 2 mid_value = nums[mid] left_value = nums[left] right_value = nums[right] # 如果中间的值等于目标值，直接返回索引 if mid_value == target: return mid # 判断左侧是否有序 if left_value <= mid_value: # 左侧是有序的 # 判断目标值是否在左侧的有序区间内 if left_value <= target < mid_value: right = mid - 1 # 目标在左侧，移动右指针 else: left = mid + 1 # 目标不在左侧，移动左指针 else: # 右侧是有序的 # 判断目标值是否在右侧的有序区间内 if mid_value < target <= right_value: left = mid + 1 # 目标在右侧，移动左指针 else: right = mid - 1 # 目标不在右侧，移动右指针 # 如果循环结束还没找到目标值，返回-1 return -1
代码解释
- 初始化和条件判断：设置左右指针分别指向数组的起始和结束位置。如果数组为空，直接返回-1。
- 计算中值和判断有序区间：每次循环计算中间索引
mid和对应的值mid_value，并判断左侧或右侧哪个区间是有序的。 - 目标值位置判断：根据目标值
target与中值mid_value的比较结果以及确定的有序区间，来决定是向左区间搜索还是向右区间搜索。 - 更新指针位置：根据上述判断，更新左指针或右指针的位置，以缩小搜索区间。
- 返回结果：循环结束如果没有找到目标值，则返回-1。
性能分析
- 时间复杂度：O(logn)，其中
n是数组长度。该算法保持了二分查找的时间复杂度，因为每次操作都将搜索区间减半。 - 空间复杂度：O(1)，算法只使用了固定的额外空间。
结论
“搜索旋转排序数组”问题展示了二分查找在复杂场景下的应用。理解数组的分段有序性是解决问题的关键，本题的解法不仅适用于旋转排序数组，也加深了对二分查找应用的理解。优化后的算法尽管在理论的时间复杂度上看不出变化（如都是 O(logn)），实际的运行时间、系统资源利用率及代码的质量和可维护性可能有显著改进。这种改进特别在大数据量处理和高性能计算环境中非常重要。
欢迎关注微信公众号 数据分析螺丝钉
