Modified Binary Search (修改版二分搜索)

Modified Binary Search（修改版二分查找）是对经典的二分查找算法的改进，主要用于解决一些在普通二分查找中难以处理的问题。普通的二分查找主要用于在有序数组中查找某个元素的位置，而修改版二分查找则是在更复杂的情境下使用，比如处理一些特殊的条件或不直接寻找元素的位置。

经典二分查找回顾

首先，我们来回顾一下经典的二分查找算法，它的基本思想是：

1. 在一个已经排好序的数组中，查找一个目标元素。
2. 每次将搜索范围（数组区间）分成两半，比较目标元素和当前中间元素：
   • 如果目标元素比中间元素小，就继续在左半边查找。
   • 如果目标元素比中间元素大，就继续在右半边查找。
3. 反复执行，直到找到目标元素，或者确定目标元素不存在。

Modified Binary Search 的不同之处：

修改版二分查找一般不是直接查找某个目标值，而是解决一些更复杂的问题，比如：

• 查找某个元素的最左位置（比如，找到数组中第一个等于目标的元素）。
• 查找某个元素的最右位置（比如，找到数组中最后一个等于目标的元素）。
• 在有序数组中找到第一个大于目标值或第一个小于目标值的位置。
• 处理有一些特殊的条件（如一些排序的变体或旋转过的数组）。

举个例子：

假设有一个有重复元素的已排序数组， [1, 2, 2, 2, 3, 4, 5]，我们要找到目标值 2 的最左位置。普通的二分查找找到的是任意一个 2，但我们想找到它在数组中的第一个位置。

使用修改版二分查找的步骤：

1. 经典二分查找正常进行：找到中间元素（比如 2），如果它是目标值，继续检查左半边，而不是立刻返回。
2. 一旦找到目标值后，我们不会立即返回，而是继续在左边的子数组中查找，以确保找到最左边的位置。
3. 最终返回最左边目标值的位置。

代码示例（查找第一个出现的位置）：

def find_first_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            result = mid  # 找到目标值，保存位置
            right = mid - 1  # 继续在左边查找
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

Modified Binary Search 的应用场景：

1. 查找元素的最左/最右位置：比如在排序的数组中查找某个数字第一次出现的位置，或者最后一次出现的位置。
2. 查找边界：比如查找第一个大于某个值的元素，或者查找第一个小于某个值的元素。
3. 解决旋转数组的问题：比如在旋转过的有序数组中查找一个元素的正确位置。

总结：

Modified Binary Search 是对传统二分查找的改进，处理的是一些特殊的查询条件，如找到目标元素的最左或最右位置，或者查找满足某种条件的元素位置。这种算法保持了二分查找的时间复杂度优势（O(log n)），但通过一些细节修改，解决了更复杂的查找问题。

LeetCode 相关题目:

已完成题目: