Binary Search 二分查找算法：逻辑的舞蹈，二分法的精准步伐

Binary Search 二分查找算法：逻辑的舞蹈，二分法的精准步伐

二分查找算法，也称为二分搜索算法（Binary Search），是一种在有序数组中查找特定元素的高效算法。它通过反复将搜索区间减半来快速定位目标值。二分查找算法的效率远高于线性搜索，因为它每次比较都能排除掉一半的搜索空间。

算法原理：切割问题的艺术，二分法的优雅

二分查找算法的原理基于一个简单的观察：在有序数组中，如果目标值小于当前中间值，则目标值只可能位于中间值的左侧；反之，如果目标值大于当前中间值，则目标值只可能位于中间值的右侧。通过这种方式，每次比较都可以排除掉一半的搜索空间，从而极大地提高查找效率。

1. 有序性前提：二分查找算法的前提是数组必须是有序的。有序性可以是升序或降序，但在整个查找过程中，数组的顺序必须保持一致。

2. 初始化指针：算法开始时，设置两个指针，一个指向数组的第一个元素（low），另一个指向数组的最后一个元素（high）。这两个指针定义了当前的搜索范围。

3. 中间值的计算：在每次迭代中，计算low和high之间的中间位置mid，通常使用(low + high) / 2来确定。这个位置的值将用于与目标值进行比较。

4. 比较与决策：

   • 如果arr[mid]等于目标值，那么查找成功，返回mid作为目标值的位置。
   • 如果arr[mid]小于目标值，那么目标值位于mid的右侧，因此将low更新为mid + 1，缩小搜索范围到右侧。
   • 如果arr[mid]大于目标值，那么目标值位于mid的左侧，因此将high更新为mid - 1，缩小搜索范围到左侧。

5. 迭代过程：重复上述比较和决策过程，直到low大于high，此时表示查找失败，目标值不在数组中。

6. 终止条件：算法的终止条件是low超过high，这时可以确定目标值不在数组中，或者已经找到目标值。

算法分析

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

代码实现详解

二分法的基本思想非常简单，但在具体实现的过程中需要注意边界值问题，以及循环终止条件的判断。下面将以LeetCode题目34. 在排序数组中查找元素的第一个和最后一个位置为例，介绍二分查找算法的一种实现过程。

C 语言实现代码如下：

int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
    // 分配一个大小为2的整数数组，用于存储目标值的起始和结束位置
    int *res = (int*) malloc (sizeof(int) * 2);
    // 初始化结果数组的两个元素为-1，表示未找到目标值
    res[0] = -1; res[1] = -1;
    // 设置返回数组的大小为2
    *returnSize = 2;

    // 定义变量用于存储目标值的起始和结束位置
    int index1, index2;
    // 初始化起始位置为-1，表示数组的左侧界
    index1 = -1;
    // 初始化结束位置为数组的长度，表示数组的右侧界
    index2 = numsSize;

    // 使用二分查找算法查找目标值的起始位置
    while (index1 + 1 != index2) {
        // 计算中间索引
        int tempIndex = (index1 + index2) / 2;
        // 如果中间索引小于0，则跳出循环，因为数组索引从0开始
        if (tempIndex < 0) break;;
        // 如果中间索引处的值大于等于目标值，则将结束位置更新为中间索引
        if (nums[tempIndex] >= target) index2 = tempIndex;
        // 否则，将起始位置更新为中间索引
        else index1 = tempIndex;
    }
    // 如果找到目标值，则更新结果数组的第一个元素为起始位置
    if (index2 < numsSize && nums[index2] == target) res[0] = index2;

    // 重置起始和结束位置，用于查找目标值的结束位置
    index1 = -1, index2 = numsSize;

    // 使用二分查找算法查找目标值的结束位置
    while (index1 + 1 != index2) {
        // 计算中间索引
        int tempIndex = (index1 + index2) / 2;
        // 如果中间索引小于0，则跳出循环
        if (tempIndex < 0) break;
        // 如果中间索引处的值大于目标值，则将结束位置更新为中间索引
        if (nums[tempIndex] > target) index2 = tempIndex;
        // 否则，将起始位置更新为中间索引
        else index1 = tempIndex;
    }
    // 如果找到目标值，则更新结果数组的第二个元素为结束位置
    if (index1 >= 0 && nums[index1] == target) res[1] = index1;

    // 返回结果数组
    return res;
}

Python 实现代码如下：

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # 初始化结果数组的两个元素为-1，表示未找到目标值
        res = [-1, -1]
        # 设置起始位置为-1，表示数组的左侧界
        index1 = -1
        # 设置结束位置为数组的长度，表示数组的右侧界
        index2 = len(nums)

        # 使用二分查找算法查找目标值的起始位置
        while index1 + 1 != index2:
            # 计算中间索引
            tempIndex = (index1 + index2) // 2
            # 如果中间索引小于0，则跳出循环
            if tempIndex < 0: break
            # 如果中间索引处的值大于等于目标值，则将结束位置更新为中间索引
            if nums[tempIndex] >= target: index2 = tempIndex
            # 否则，将起始位置更新为中间索引
            else: index1 = tempIndex
        # 如果找到目标值，则更新结果数组的第一个元素为起始位置
        if index2 < len(nums) and nums[index2] == target: res[0] = index2

        # 重置起始和结束位置，用于查找目标值的结束位置
        index1, index2 = -1, len(nums)

        # 使用二分查找算法查找目标值的结束位置
        while index1 + 1 != index2:
            # 计算中间索引
            tempIndex = (index1 + index2) // 2
            # 如果中间索引小于0，则跳出循环
            if tempIndex < 0: break
            # 如果中间索引处的值大于目标值，则将结束位置更新为中间索引
            if nums[tempIndex] > target: index2 = tempIndex
            # 否则，将起始位置更新为中间索引
            else: index1 = tempIndex
        # 如果找到目标值，则更新结果数组的第二个元素为结束位置
        if index1 >= 0 and nums[index1] == target: res[1] = index1

        return res

LeetCode相关题目：
34. 在排序数组中查找元素的第一个和最后一个位置
278. 第一个错误的版本
35. 搜索插入位置