二分查找算法详解：从基础到进阶

创作时间:

作者:

@小白创作中心

二分查找算法详解：从基础到进阶

引用

来源

https://www.cnblogs.com/lrc123/p/18093400

二分查找算法是计算机科学中一种非常基础且高效的搜索算法，广泛应用于各种数据结构和算法问题中。本文将从基础到进阶，全面介绍二分查找的各种变体及其应用场景，帮助读者深入理解这一经典算法。

二分查找算法思想

二分查找算法要求待查找的数组必须是有序的。其基本思想是通过不断缩小查找范围来快速定位目标值：

定义左右边界索引l、r，中间索引m=(l+r)/2
判断arr[m]与待查找值target的大小关系：

如果target<arr[m]，则证明待查找值在中间索引左侧，减少右边界索引r=m-1
如果target>arr[m]，则证明待查找值在中间索引右侧，增加左边界索引l=m+1
如果target=arr[m]，则证明找到待查找值，返回对应索引

当l>r时，表示没有找到目标值，返回-1

基础版二分查找代码实现

public static int binarySearch(int [] arr,int target){
    int l = 0, r=arr.length-1;
    while (l<=r){
        int m = (l+r)>>>1;
        if(target<arr[m]){
            r=m-1;
        }else if(arr[m]<target){
            l=m+1;
        }else {
            return m;
        }
    }
    return -1;
}

基础版二分查找性能分析

最好情况：O(1)，第一次循环的值就是待查找值
最坏情况：O(log(n))

平衡版二分查找

在基础版二分查找中，当目标值位于数组左侧时，查找效率较高；而位于右侧时，效率较低。平衡版二分查找通过调整查找策略，使左右两侧的查找效率保持一致：

采用左闭右开区间，即左边界索引l可能是查找目标，而右边界索引r不可能是查找目标
在循环外判断最终的l是否为目标值

平衡版二分查找代码实现

public static int binarySearch2(int [] arr,int target){
    int l = 0, r=arr.length;
    while (1 <r-l ){
        int m = (l+r)>>>1;
        if(target<arr[m]){
            r=m;
        }else {
            l=m;
        }
    }
    if(arr[l]==target){
        return l;
    }else {
        return -1;
    }
}

最左、右侧匹配的二分查找（LeftRightMost）

在某些场景下，我们可能需要找到所有相同值中的最左侧或最右侧的元素。以下是两种实现方式：

最左侧匹配的二分查找（LeftMost）

public static int binarySearchLeftMost(int [] arr,int target){
    int l = 0, r=arr.length-1;
    int candidate=-1;
    while (l<=r){
        int m = (l+r)>>>1;
        if(target<arr[m]){
            r=m-1;
        }else if(arr[m]<target){
            l=m+1;
        }else {
            //找到元素了，不直接返回m，而是记录候选者位置，继续缩小查找范围
           candidate = m;
           r = m-1;
        }
    }
    return candidate;
}

最左侧匹配的二分查找（LeftMost）-返回特定值

public static int binarySearchLeftMost2(int [] arr,int target){
    int l = 0, r=arr.length-1;
    while (l<=r){
        int m = (l+r)>>>1;
        if(target<=arr[m]){
            //无论target是否找到还是没找到，都继续缩小范围
            r=m-1;
        } else {
            l=m+1;
        }
    }
    //返回的l是≥target的最左侧索引
    return l;
}

最右侧匹配的二分查找（RightMost）

public static int binarySearchRightMost(int [] arr,int target){
    int l = 0, r=arr.length-1;
    int candidate=-1;
    while (l<=r){
        int m = (l+r)>>>1;
        if(target<arr[m]){
            r=m-1;
        }else if(arr[m]<target){
            l=m+1;
        }else {
            //找到元素了，不直接返回m，而是记录候选者位置，继续缩小查找范围
            candidate = m;
            l = m+1;
        }
    }
    return candidate;
}

最右侧匹配的二分查找（RightMost）-返回特定位置

public static int binarySearchRightMost2(int [] arr,int target){
    int l = 0, r=arr.length-1;
    while (l<=r){
        int m = (l+r)>>>1;
        if(target<arr[m]){
            r=m-1;
        }else {
            //无论target是否找到还是没找到，都继续缩小范围
            l=m+1;
        }
    }
    //返回的l-1是≤target的最右侧索引
    return l-1;
}