二分搜索大师课：Python编程实现与性能提升

# 1. 二分搜索算法概述

二分搜索算法，作为计算机科学领域中一个历史悠久且应用广泛的算法，它提供了在有序集合中高效查找特定元素的方法。其基本思想是在一个已经排序的数组中，通过反复比较和缩小查找范围来定位目标元素。相比于简单的遍历查找，二分搜索大大减少了搜索时间，其最坏情况下的时间复杂度为O(log n)，在处理大数据集时尤其高效。

本章将简要介绍二分搜索算法的起源、基本概念和应用场景，为接下来的章节打下理论基础。我们将探讨算法的适用条件，并且介绍一些常见的二分搜索变体。通过这些介绍，读者将对二分搜索算法有一个初步的认识，并激发进一步深入研究的兴趣。

# 2. 二分搜索算法的理论基础

## 2.1 二分搜索算法原理
### 2.1.1 算法逻辑和步骤

二分搜索算法，又称折半搜索算法，是一种在有序数组中查找特定元素的高效算法。其基本思想是在每次迭代中将搜索区间减半，直到找到目标值或者确定目标值不存在为止。二分搜索算法的步骤如下：

1. **初始化**：设置搜索的起始点和结束点，分别标记为 `left` 和 `right`，通常 `left` 为0，`right` 为数组长度减1。
2. **循环条件**：当 `left` 小于等于 `right` 时，进行循环。
3. **计算中间点**：找到当前搜索区间的中间位置，标记为 `mid`，可以通过 `(left + right) // 2` 实现。
4. **比较中间值与目标值**：
- 如果中间值 `array[mid]` 等于目标值 `target`，则返回 `mid`。
- 如果中间值小于目标值，则说明目标值在中间值的右侧，因此将 `left` 移至 `mid + 1`。
- 如果中间值大于目标值，则说明目标值在中间值的左侧，因此将 `right` 移至 `mid - 1`。
5. **终止条件**：如果 `left` 大于 `right`，则表示整个搜索区间已经不存在目标值，返回一个表示未找到的标记值，如 `-1`。

### 2.1.2 算法的时间复杂度分析

二分搜索算法的时间复杂度为 `O(log n)`，其中 `n` 是数组中元素的数量。这是因为在每次迭代中，搜索区间都会被减半，因此算法的迭代次数与数组长度的对数成正比。

为了具体分析，考虑最坏情况下的迭代次数，即每次迭代我们都无法找到目标值，需要将搜索区间减半直到区间为空。假设在第 `i` 次迭代后搜索区间为空，那么有：

n / 2^i = 1

解此方程得到迭代次数 `i` 等于 `log2(n)`，因此二分搜索的时间复杂度为 `O(log n)`。

## 2.2 二分搜索变体与应用场景

### 2.2.1 下界二分搜索

在某些情况下，我们需要在有序数组中找到一个元素的最左（或最右）出现位置，这就是下界二分搜索（Lower Bound Binary Search）的应用场景。例如，在一个只有0和1组成的有序数组中找到第一个1的位置。

下界二分搜索的基本步骤和普通二分搜索类似，但是当找到目标值时，不会立即返回，而是将右指针左移，继续搜索是否还有相同的值在左侧，以确保找到最左的位置。

### 2.2.2 上界二分搜索

上界二分搜索（Upper Bound Binary Search）则是在有序数组中找到一个元素的最右（或最左）出现位置。例如，在一个递增数组中寻找一个数的最后出现位置。

上界二分搜索的处理逻辑是，当找到目标值时，将左指针右移，继续搜索是否还有相同的值在右侧，以确保找到最右的位置。

### 2.2.3 旋转数组的二分搜索

如果一个有序数组经过旋转，形成了两个有序的子数组，那么传统的二分搜索算法无法直接应用。针对这种情况，我们需要使用旋转数组的二分搜索。

在旋转数组的二分搜索中，首先判断 `array[left]` 和 `array[right]` 的关系：

- 如果 `array[left]` 小于 `array[right]`，说明数组没有旋转，可以使用传统二分搜索算法。
- 否则，数组已经旋转，需要决定搜索目标值时应该在左半部分还是右半部分。可以通过比较 `array[mid]` 和 `array[left]`、`array[right]` 来决定。

实现旋转数组的二分搜索需要对二分搜索算法进行适当的修改，以适应数组旋转带来的复杂性。

## 代码实现

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

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

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

def rotated_array_search(array, target):
    if len(array) == 0:
        return -1
    left, right = 0, len(array) - 1
    while left <= right:
        mid = (left + right) // 2
        if array[mid] == target:
            return mid
        # Decide whether to search in left or right half
        if array[left] <= array[mid]:
            if array[left] <= target < array[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if array[mid] < targe