企业官网建设流程全解析

1. 项目概述

今天要聊的是LeetCode hot100中两道经典的数组搜索问题："在排序数组中查找元素的第一个和最后一个位置"（Find First and Last Position of Element in Sorted Array）和"搜索旋转排序数组"（Search in Rotated Sorted Array）。这两道题在面试中出现频率极高，也是检验算法基本功的试金石。

作为刷过300+道LeetCode的老手，我发现很多初学者在面对这两道题时容易陷入暴力解法的思维定式。实际上，它们都是二分查找（Binary Search）的经典变种，考察的是对二分思想的灵活运用能力。本文将带你深入理解这两道题的解题思路，并分享我在实际刷题中总结的优化技巧。

2. 核心需求解析

2.1 问题一：在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组nums，和一个目标值target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值，返回[-1, -1]。

示例：

输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]

2.2 问题二：搜索旋转排序数组

整数数组nums按升序排列，数组中的值互不相同。在传递给函数之前，nums在预先未知的某个下标k（0 <= k < nums.length）上进行了旋转，使数组变为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]。给你旋转后的数组nums和一个整数target，如果nums中存在这个目标值target，则返回它的索引，否则返回-1。

示例：

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

3. 解题思路与算法选择

3.1 问题一的二分查找解法

对于查找元素的第一个和最后一个位置，最直观的思路是使用线性扫描，但这需要O(n)的时间复杂度。考虑到数组是有序的，我们可以使用二分查找将时间复杂度优化到O(log n)。

关键点在于如何修改标准的二分查找来找到目标值的边界。标准二分查找在找到目标值后会立即返回，而我们需要继续搜索以确定左右边界。

3.1.1 查找左边界

def find_left_bound(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 else: right = mid - 1 return left

3.1.2 查找右边界

def find_right_bound(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] <= target: left = mid + 1 else: right = mid - 1 return right

3.2 问题二的旋转数组搜索解法

旋转排序数组的特点是它由两个有序的子数组组成，且第一个子数组的所有元素都大于第二个子数组的所有元素。我们可以利用这个特性来修改二分查找算法。

关键思路是：

1. 找到旋转点（即数组中的最小值）
2. 确定target位于哪个有序子数组
3. 在相应的子数组中进行标准二分查找

3.2.1 查找旋转点

def find_rotate_index(nums): left, right = 0, len(nums) - 1 if nums[left] < nums[right]: return 0 while left <= right: mid = left + (right - left) // 2 if nums[mid] > nums[mid + 1]: return mid + 1 else: if nums[mid] < nums[left]: right = mid - 1 else: left = mid + 1 return 0

3.2.2 二分搜索实现

def search(nums, target): def binary_search(left, right): while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1 n = len(nums) if n == 0: return -1 if n == 1: return 0 if nums[0] == target else -1 rotate_index = find_rotate_index(nums) # 如果target是最小值 if nums[rotate_index] == target: return rotate_index # 如果数组没有旋转，在整个数组搜索 if rotate_index == 0: return binary_search(0, n - 1) if target < nums[0]: # 在右半部分搜索 return binary_search(rotate_index, n - 1) # 在左半部分搜索 return binary_search(0, rotate_index)

4. 代码实现与优化

4.1 问题一的完整实现

def searchRange(nums, target): def find_left(): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 else: right = mid - 1 return left def find_right(): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] <= target: left = mid + 1 else: right = mid - 1 return right left_idx = find_left() right_idx = find_right() if left_idx <= right_idx and right_idx < len(nums) and nums[left_idx] == target and nums[right_idx] == target: return [left_idx, right_idx] return [-1, -1]

4.2 问题二的优化实现

def search(nums, target): 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

这个优化版本只需要一次二分查找，时间复杂度为O(log n)，空间复杂度为O(1)。

5. 边界条件与测试用例

5.1 问题一的边界情况

1. 数组为空
2. 目标值不存在于数组中
3. 目标值只出现一次
4. 目标值出现多次
5. 目标值是数组的最小值或最大值
6. 目标值出现在数组开头或结尾

测试用例示例：

assert searchRange([], 0) == [-1, -1] assert searchRange([1,2,3], 4) == [-1, -1] assert searchRange([1,2,2,3], 2) == [1, 2] assert searchRange([1,1,1,1], 1) == [0, 3] assert searchRange([1,2,3,3,3,4,5], 3) == [2, 4]

5.2 问题二的边界情况

1. 数组未旋转
2. 数组旋转了n-1次（相当于没有旋转）
3. 目标值等于旋转点
4. 目标值不存在于数组中
5. 数组只有一个元素
6. 目标值是数组的最小值或最大值

测试用例示例：

assert search([4,5,6,7,0,1,2], 0) == 4 assert search([1,2,3,4,5], 3) == 2 assert search([5,1,3], 5) == 0 assert search([1], 0) == -1 assert search([4,5,6,7,8,1,2,3], 8) == 4

6. 复杂度分析与算法比较

6.1 时间复杂度

两个问题的优化解法都基于二分查找，因此时间复杂度均为O(log n)，其中n是数组的长度。

6.2 空间复杂度

两个问题的解法都只使用了常数级别的额外空间，因此空间复杂度为O(1)。

6.3 与其他算法的比较

1. 线性扫描法：时间复杂度O(n)，实现简单但效率低
2. 哈希表法：需要额外O(n)空间，且破坏了数组有序的特性
3. 标准二分查找：无法处理边界条件和旋转数组的情况

相比之下，我们提出的解法在时间和空间复杂度上都是最优的。

7. 常见错误与调试技巧

7.1 问题一的常见错误

1. 边界条件处理不当：忘记检查数组为空或目标值不存在的情况
2. 无限循环：二分查找的终止条件设置错误
3. 边界判断错误：找到的左右边界可能超出数组范围或不符合条件

调试技巧：

• 在循环中添加打印语句，观察left、right和mid的变化
• 使用小规模的测试用例手动模拟算法执行过程
• 特别注意当left == right时的处理逻辑

7.2 问题二的常见错误

1. 旋转点判断错误：没有正确处理数组未旋转或完全旋转的情况
2. 搜索范围选择错误：错误判断target位于哪个有序子数组
3. 索引越界：在访问nums[mid+1]时可能超出数组范围

调试技巧：

• 先单独测试旋转点查找函数是否正确
• 绘制数组的折线图帮助理解旋转后的结构
• 添加断言检查数组是否确实在旋转点处有序

8. 实际应用与扩展

8.1 实际应用场景

1. 数据库查询优化：在有序数据集中快速定位记录范围
2. 日志分析：在时间戳有序的日志中查找特定时间范围内的事件
3. 游戏开发：在排序的分数表中查找玩家排名
4. 金融分析：在有序的时间序列数据中查找特定价格区间

8.2 问题变种与扩展

1. 允许重复元素的旋转数组搜索
2. 查找旋转排序数组中的最小值
3. 在旋转排序数组中搜索目标值的范围
4. 二维矩阵中的二分查找
5. 在未知大小的排序数组中搜索

8.3 相关LeetCode题目推荐

1. 33. 搜索旋转排序数组
2. 81. 搜索旋转排序数组 II（含重复元素）
3. 153. 寻找旋转排序数组中的最小值
4. 154. 寻找旋转排序数组中的最小值 II（含重复元素）
5. 162. 寻找峰值
6. 34. 在排序数组中查找元素的第一个和最后一个位置
7. 35. 搜索插入位置
8. 74. 搜索二维矩阵
9. 240. 搜索二维矩阵 II

9. 刷题心得与建议

经过多次练习这两道题目，我总结出以下几点经验：

1. 理解二分查找的本质：每次排除一半的搜索空间，而不仅仅是"找中间值"
2. 画图辅助：对于旋转数组问题，画出折线图能帮助理解数组结构
3. 边界测试：特别注意空数组、单元素数组、全相同元素数组等边界情况
4. 分步验证：先单独测试辅助函数（如旋转点查找），再整合到主算法中
5. 变量命名：使用有意义的变量名（如left_bound而不是简单的left）提高代码可读性

对于面试准备，建议：

1. 先写出标准二分查找模板，再根据题目要求进行修改
2. 明确循环不变量（loop invariant）是什么
3. 思考如何通过一次二分查找解决问题，而不是多次
4. 准备好时间复杂度和空间复杂度的分析
5. 准备几个有代表性的测试用例，包括边界情况

最后，记住这两道题的解法不是死记硬背的，而是要理解二分查找的灵活应用。在实际面试中，面试官可能会提出各种变种问题，只有真正理解了算法原理，才能灵活应对。