作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
输入格式
- nums：一个可能包含重复元素的整数数组。
- target：一个整数，表示需要搜索的目标值。
输出格式
- 返回一个布尔值，表示目标值是否存在于数组中。
示例
示例 1
输入: nums = [2,5,6,0,0,1,2], target = 0 输出: true
示例 2
输入: nums = [2,5,6,0,0,1,2], target = 3 输出: false
方法一：线性搜索
解题步骤
- 直接遍历：遍历整个数组，直接比较每个元素是否等于目标值。
完整的规范代码
def search(nums, target): """ 线性搜索，直接遍历数组 :param nums: List[int], 输入的数组 :param target: int, 需要搜索的目标值 :return: bool, 目标值是否存在于数组中 """ return target in nums # 示例调用 print(search([2,5,6,0,0,1,2], 0)) # 输出: true print(search([2,5,6,0,0,1,2], 3)) # 输出: false
算法分析
- 时间复杂度：(O(n))，在最坏情况下需要遍历整个数组。
- 空间复杂度：(O(1))，不需要额外的存储空间。
方法二：二分搜索
解题步骤
- 二分搜索：尽管数组被旋转过，但仍然可以通过比较中间元素与端点来决定搜索方向。
- 处理重复元素：由于存在重复元素，当遇到中间元素等于端点时，不能确定哪部分是有序的，需要逐步缩小范围。
完整的规范代码
def search(nums, target): """ 二分搜索在可能存在重复元素的旋转排序数组中查找目标值 :param nums: List[int], 输入的数组 :param target: int, 需要搜索的目标值 :return: bool, 目标值是否存在于数组中 """ if not nums: return False left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return True if nums[left] == nums[mid] == nums[right]: left += 1 right -= 1 elif 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 False # 示例调用 print(search([2,5,6,0,0,1,2], 0)) # 输出: true print(search([2,5,6,0,0,1,2], 3)) # 输出: false
算法分析
- 时间复杂度：平均情况 (O(\log n))，但在最坏情况下由于重复元素的存在可能退化到 (O(n))。
- 空间复杂度：(O(1))，使用常数空间进行计算。
方法三：修改的二分搜索
解题步骤
- 优化二分搜索：对二分搜索进行修改，处理数组中的重复元素和旋转的情况。
- 区间收缩：当无法确定哪部分有序时，适当缩小搜索区间。
完整的规范代码
def search(nums, target): """ 修改的二分搜索，优化处理旋转数组和重复元素 :param nums: List[int], 输入的数组 :param target: int, 需要搜索的目标值 :return: bool, 目标值是否存在于数组中 """ left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return True # 判断哪一半是有序的 if nums[left] < nums[mid]: # 左半部分有序 if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 elif nums[left] > nums[mid]: # 右半部分有序 if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1 else: # 无法判断哪半部分有序 left += 1 return False # 示例调用 print(search([2,5,6,0,0,1,2], 0)) # 输出: true print(search([2,5,6,0,0,1,2], 3)) # 输出: false
算法分析
- 时间复杂度：在无重复元素的情况下为 (O(\log n))，但当存在大量重复元素时可能接近 (O(n))。
- 空间复杂度：(O(1))，只使用了有限的额外空间。
方法四：哈希表
解题步骤
- 使用哈希表：将所有元素存储在哈希表中，然后检查目标值是否存在于哈希表中。
完整的规范代码
def search(nums, target): """ 使用哈希表检查目标值是否存在于数组中 :param nums: List[int], 输入的数组 :param target: int, 需要搜索的目标值 :return: bool, 目标值是否存在于数组中 """ return target in set(nums) # 示例调用 print(search([2,5,6,0,0,1,2], 0)) # 输出: true print(search([2,5,6,0,0,1,2], 3)) # 输出: false
算法分析
- 时间复杂度：(O(n))，建立哈希表需要 (O(n)) 时间。
- 空间复杂度：(O(n))，存储所有元素需要 (O(n)) 空间。
方法五：递归分治
解题步骤
- 递归分治：将数组分为两部分，分别搜索，递归处理每部分。
- 处理重复和旋转：在递归过程中处理重复元素和数组的旋转状态。
完整的规范代码
def search(nums, target): """ 使用递归分治法搜索旋转排序数组 :param nums: List[int], 输入的数组 :param target: int, 需要搜索的目标值 :return: bool, 目标值是否存在于数组中 """ def helper(l, r): if l > r: return False mid = (l + r) // 2 if nums[mid] == target: return True # 分治递归 return helper(l, mid - 1) or helper(mid + 1, r) return helper(0, len(nums) - 1) # 示例调用 print(search([2,5,6,0,0,1,2], 0)) # 输出: true print(search([2,5,6,0,0,1,2], 3)) # 输出: false
算法分析
- 时间复杂度：(O(n))，在最坏情况下可能需要搜索整个数组。
- 空间复杂度：(O(\log n))，递归栈的深度依赖于数组长度。
不同算法的优劣势对比
| 特征 | 方法一：线性搜索 | 方法二：二分搜索 | 方法三：修改的二分搜索 | 方法四：哈希表 | 方法五：递归分治 |
| 时间复杂度 | (O(n)) | (O(\log n)) ~ (O(n)) | (O(\log n)) ~ (O(n)) | (O(n)) | (O(n)) |
| 空间复杂度 | (O(1)) | (O(1)) | (O(1)) | (O(n)) | |
| 优势 | 简单直观，适用于所有情况 | 在没有重复元素的情况下非常高效 | 可以有效处理重复元素和旋转 | 快速查找，适用于大数据 | 利用递归处理复杂的重复和旋转问题 |
| 劣势 | 效率较低，尤其是在数组较长时 | 在重复元素多的情况下性能下降 | 较复杂，需要处理多种边界情况 | 需要额外的存储空间 | 可能造成栈溢出，效率不稳定 |
应用示例
搜索算法通常用于：
- 数据库查询：特别是在处理包含大量重复元素的数据集时，有效的搜索算法可以极大地提高查询效率。
- 实时系统：在需要快速响应的系统中，高效的搜索算法可以减少延迟，提高用户满意度。
- 数据分析：在数据科学中，经常需要在大规模数据集中寻找特定的模式或信息，优化的搜索算法在这种场景下尤为重要。
每种方法都有其适用场景，选择合适的算法依赖于具体的应用需求、数据的特性以及性能的要求。
欢迎关注微信公众号 数据分析螺丝钉
