【算法】深入理解二分查找算法及其实现

【算法】深入理解二分查找算法及其实现

引用

CSDN

1.

https://blog.csdn.net/qq_33502371/article/details/140370188

二分查找算法是一种在有序数组中查找特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且同样从中间元素开始比较。这种搜索算法每一次比较都使搜索范围缩小一半。

二分查找算法详解

假设我们有一个升序排列的数组 arr 和一个目标值 target，我们的目标是在 arr 中找到 target 的位置。算法步骤如下：

1. 初始化两个指针 left 和 right，分别指向数组的第一个元素和最后一个元素。
2. 当 left <= right 时，执行循环：

• 计算中间位置 mid = (left + right) // 2。
• 如果 arr[mid] == target，则返回 mid。
• 如果 arr[mid] < target，则将 left 设置为 mid + 1。
• 如果 arr[mid] > target，则将 right 设置为 mid - 1。

3. 如果没有找到目标值，返回 -1 表示未找到。

实现代码

下面我们将用Python和JavaScript两种语言来实现二分查找算法。

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

# 测试代码
arr = [1, 3, 5, 7, 9, 11]
target = 7
print(binary_search(arr, target))  # 输出: 3

JavaScript 实现

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

// 测试代码
const arr = [1, 3, 5, 7, 9, 11];
const target = 7;
console.log(binarySearch(arr, target));  // 输出: 3

扩展：二分查找的变体与高级应用

旋转数组的二分查找

在标准的二分查找中，数组是单调递增的。但在一些场景下，数组可能是经过旋转的，即数组的一部分被移动到了数组的另一端。例如，[3, 4, 5, 1, 2] 就是一个经过旋转的有序数组。在这种情况下，我们如何进行有效的二分查找呢？

Python 实现

def rotated_binary_search(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

# 测试代码
arr = [4, 5, 6, 7, 0, 1, 2]
target = 0
print(rotated_binary_search(arr, target))  # 输出: 4

寻找最接近的元素

有时我们可能需要在数组中找到最接近给定目标值的元素。这可以通过稍微修改二分查找算法来实现。

Python 实现

def find_closest(arr, target):
    left, right = 0, len(arr) - 1
    closest = None
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return arr[mid]
        
        if closest is None or abs(target - arr[mid]) < abs(target - closest):
            closest = arr[mid]
            
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return closest

# 测试代码
arr = [1, 2, 3, 4, 5]
target = 3.5
print(find_closest(arr, target))  # 输出: 3 或 4，取决于具体实现

多次出现的元素查找

当数组中有重复的元素时，我们可能需要找到第一个或最后一个出现的指定元素。

Python 实现

def find_first_occurrence(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  # 继续向左查找
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return result

# 测试代码
arr = [1, 2, 2, 2, 3, 4, 5]
target = 2
print(find_first_occurrence(arr, target))  # 输出: 1

优势与缺点

优势

• 高效性：二分查找的时间复杂度为O(log n)，这意味着即使在非常大的数据集中，算法也能迅速定位目标元素。相比之下，线性搜索的时间复杂度为O(n)，在数据量庞大时效率低下。
• 低比较次数：二分查找每次迭代都将搜索空间减半，因此所需的比较次数远低于线性搜索。
• 稳定性能：在平均和最坏情况下，二分查找都表现出色，不会像某些其他算法那样在特定输入下性能显著下降。

缺点

• 有序性要求：二分查找依赖于数据的有序性。如果数据无序，需要先进行排序，这会增加额外的时间成本。
• 插入与删除困难：在有序数组中进行插入或删除操作时，可能需要移动大量元素，影响效率。
• 空间限制：二分查找最适合静态数据结构，如数组。在链表等动态数据结构上，由于随机访问的限制，其效率会大打折扣。

实际应用案例

• 数据库索引：数据库系统利用类似于二分查找的策略在索引上快速定位记录，极大提高了查询速度。
• 编译器：在编译过程中，二分查找用于在符号表中快速查找变量和函数。
• 游戏开发：在游戏引擎中，二分查找用于快速查找碰撞检测、地图数据检索等。
• 数据挖掘与机器学习：在特征选择和模型训练中，二分查找可用于优化参数寻优。

参考文献

• "A Comparison of Sorting Algorithms for the Alpha 21164" - 这篇论文虽然主要关注排序算法，但也讨论了二分查找算法在搜索已排序数据集中的效率。
• "The Art of Computer Programming, Volume 3: Sorting and Searching" - 唐纳德·克努特的著作，详细介绍了二分查找和其他搜索算法。
• "Data Structures and Algorithm Analysis in C++" by Mark Allen Weiss - 这本书涵盖了包括二分查找在内的多种数据结构和算法。