二分查找变种题攻略：旋转数组与搜索插入
二分查找是一种高效的查找算法，其基本思想是将有序数组分成两半，根据目标值与中间值的比较结果，决定在数组的哪一半继续查找。在实际应用中，我们可能会遇到一些特殊的数组，如旋转数组。旋转数组是一种经过某种方式旋转的有序数组，其查找过程与普通有序数组有所不同。还有一种变种题是搜索插入，它要求在有序数组中找到目标值应该插入的位置。本文将围绕这两个变种题，探讨二分查找的优化策略。
旋转数组
问题描述
给定一个按照非降序排列的整数数组 nums，假设数组已经旋转，比如 nums = [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2]。请编写一个函数，找出这个旋转数组中的目标值 target 的索引。
解题思路
1. 初始化两个指针 left 和 right，分别指向数组的开始和结束。
2. 当 left 小于等于 right 时，计算中间索引 mid。
3. 比较中间值 nums[mid] 与目标值 target：
- 如果 nums[mid] 等于 target，返回 mid。
- 如果 nums[mid] 大于等于 nums[left]，说明左半部分有序：
- 如果 nums[left] 小于等于 target 且 nums[mid] 大于 target，说明目标值在左半部分，将 right 更新为 mid - 1。
- 否则，将 left 更新为 mid + 1。
- 如果 nums[mid] 小于等于 nums[right]，说明右半部分有序：
- 如果 nums[mid] 小于 target 且 nums[right] 大于 target，说明目标值在右半部分，将 left 更新为 mid + 1。
- 否则，将 right 更新为 mid - 1。
4. 如果循环结束后未找到目标值，返回 -1。
代码实现
python
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[mid] >= nums[left]:
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
搜索插入
问题描述
给定一个按非降序排列的整数数组 nums 和一个整数 target，请编写一个函数，在数组中找到 target 应该被插入的位置。
解题思路
1. 初始化两个指针 left 和 right，分别指向数组的开始和结束。
2. 当 left 小于等于 right 时，计算中间索引 mid。
3. 比较中间值 nums[mid] 与目标值 target：
- 如果 nums[mid] 等于 target，返回 mid。
- 如果 nums[mid] 大于 target，将 right 更新为 mid - 1。
- 如果 nums[mid] 小于 target，将 left 更新为 mid + 1。
4. 循环结束后，如果 left 等于 nums 的长度，说明 target 应该插入到数组的末尾；否则，返回 left。
代码实现
python
def searchInsert(nums, target):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid
else:
left = mid + 1
return left
总结
本文介绍了二分查找的两个变种题：旋转数组和搜索插入。通过分析问题，我们找到了相应的解题思路，并给出了代码实现。这两个变种题在面试和实际应用中都非常常见，掌握它们的解题方法对于提高编程能力具有重要意义。在实际编程过程中，我们需要根据具体问题选择合适的算法，以达到最优的性能。
Comments NOTHING