使用递增_递减函数进行二分查找：掌握核心原理

# 1. 二分查找算法概述

二分查找算法是一种高效的搜索算法，主要应用于有序数组或有序列表中。通过不断将待查找区间缩小一半的方式，逐步逼近目标值，从而快速定位目标值的位置。下表总结了二分查找算法的基本原理和特点：

| 特点 | 说明 |
| ---- | ---- |
| **递增** | 二分查找适用于递增函数，即数组或列表中元素按递增顺序排列 |
| **递减** | 二分查找同样适用于递减函数，但需要将递增函数的条件稍作调整 |
| **单调性** | 待查找数组或列表必须具有单调性，即递增或递减特性 |
| **时间复杂度** | 二分查找的时间复杂度为 O(log n)，远优于线性搜索算法 |

在后续章节中，我们将深入探讨递增函数和递减函数的二分查找实现步骤，以及如何处理边界情况和优化算法。

# 2. 递增函数的二分查找

- 理解递增函数的特点
- 递增函数的特点是函数值随着自变量的增加而增加，即$f(x) < f(y)$，其中$x < y$。
- 递增函数的二分查找实现步骤
1. 初始化左指针 `left` 和右指针 `right`，分别指向数组的起始位置和末尾位置。
2. 在每一步迭代中，计算中间元素的索引 `mid`。
3. 如果中间元素等于目标值，则返回索引值。
4. 如果中间元素小于目标值，则更新左指针为 `mid + 1`。
5. 如果中间元素大于目标值，则更新右指针为 `mid - 1`。
6. 重复上述步骤直到找到目标值或左指针大于右指针。
- 递增函数二分查找的时间复杂度分析
- 在每一步迭代中，问题规模减半，时间复杂度为O(log n)。

def binary_search_inc(nums, target):
    left, right = 0, len(nums) - 1
    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

| Input | Output |
|-------------------------- |------------ |
| [1, 3, 5, 7, 9, 11, 13] | index = 4 |
| [2, 4, 6, 8, 10] | index = -1 |

graph TD;
    A[Initialize left and right pointers] --> B{left <= right};
    B -- Yes --> C{nums[mid] == target};
    B -- No --> D{nums[mid] < target};
    D -- Yes --> E[Update left = mid + 1];
    D -- No --> F[Update right = mid - 1];
    F --> B;
    C --> G[Return mid];

# 3. 递减函数的二分查找

- **理解递减函数的特点**
递减函数在数学上表现为随着自变量增加，函数值逐渐减小的特点。在二分查找中，递减函数与递增函数相反，当中间值小于目标值时，在右侧继续搜索。
- **递减函数的二分查找实现步骤**
1. 初始化 left = 0, right = n-1，其中 n 为数组长度。
2. 当 left <= right 时，计算中间值 mid = (left + right) // 2。
3. 若 nums[mid] 等于目标值 target，则返回 mid。
4. 若 nums[mid] 大于目标值 target，则在左侧搜索，更新 right = mid - 1。
5. 若 nums[mid] 小于目标值 target，则在右侧搜索，更新 left = mid + 1。
6. 循环直至找到目标值或搜索范围缩小为空。

- **递减函数二分查找的时间复杂度分析**
递减函数的二分查找与递增函数的时间复杂度相同，均为 O(log n)，因为每次搜索都能将搜索范围缩小为上一次的一半。

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