在数据处理和算法设计的广阔天地里，二分查找（Binary Search）以其高效的搜索性能著称，尤其是在有序数组中查找特定元素时，其平均时间复杂度可达O(log n)。然而，面对日益复杂的数据结构和搜索需求，传统的二分查找算法已难以满足所有场景。本文将探讨几种Python实现的二分查找变种策略，旨在进一步提升搜索效率，拓宽其应用范围。
- 经典二分查找回顾
首先，我们回顾一下经典二分查找的基本思想：在有序数组中，通过不断将搜索区间一分为二，逐步缩小搜索范围，直至找到目标元素或确定目标不存在。
python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
- 变种一：查找第一个等于给定值的元素
在某些情况下，我们不仅需要知道元素是否存在，还需要找到它第一次出现的位置。
python
def find_first_equal(arr, target):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] >= target:
result = mid # 更新结果，但继续向左搜索
right = mid - 1
else:
left = mid + 1
return result if result != -1 and arr[result] == target else -1
- 变种二：查找最后一个等于给定值的元素
类似地，查找给定值最后一次出现的位置也很有用。
python
def find_last_equal(arr, target):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] <= target:
result = mid # 更新结果，但继续向右搜索
left = mid + 1
else:
right = mid - 1
return result if result != -1 and arr[result] == target else -1
- 变种三：旋转有序数组的搜索
当数组被旋转（如[4, 5, 6, 7, 0, 1, 2]）但仍保持两部分有序时，二分查找依然可以高效工作。
python
def search_in_rotated_array(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
# 如果中间值恰好是目标，直接返回
if arr[mid] == target:
return mid
# 判断左半部分是否有序
if arr[left] <= arr[mid]:
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
else:
# 右半部分有序
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return -1
这些二分查找的变种策略展示了如何通过调整搜索条件和边界处理，来适应更复杂的搜索场景，从而提升搜索效率和应用灵活性。在实际编程中，根据具体需求选择合适的变种策略，是成为一名高效算法开发者的关键。
