作者介绍: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)),实际的运行时间、系统资源利用率及代码的质量和可维护性可能有显著改进。这种改进特别在大数据量处理和高性能计算环境中非常重要。
欢迎关注微信公众号 数据分析螺丝钉