二分查找的4种变体

在基本的二分查找法中，我们规定给定数组是不重复且有序的（一般为升序），这几个变体的规则有些变化，仍然是升序元素，但是可以有重复元素。

变体问题：
（1）查找第一个值等给定值的元素
（2）查找最后一个值等于给定值的元素
（3）查找第一个值大于等于给定值的元素
（4）查找最后一个值小于等于给定值的元素

接下来我们就来分析一下。

（1）查找第一个值等给定值的元素
我们要找给定值，核心算法还是二分查找，但是有了具体查找条件，「第一个值等给定值的元素」，怎么才算呢？在循环中，如果我们找到的等于给定值的值，而且这个值「位于整个数组的第一个位置或者它前面那个元素小于给定值」，那么就是我们要找的。这里大家可以体会一下这个查找条件。

代码：

// 查找第一个值等于给定值的元素
function find(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    let mid;

    while(left <= right) {
        mid = Math.floor((left + right) / 2);
        if(arr[mid] > target) {
            right = mid - 1;
        } else {
            if(arr[mid] < target) {
                left = mid + 1;
            } else {
                // 剩下都是相等的情况，在这个大条件下我们加以约束
                // 如果当前元素是「处于数组第一个位置」或者「它前一个元素的值不等于给定值」，就符合要求
                if(mid === 0 || arr[mid - 1] !== target) {
                    return mid;
                } else {
                    // 不是第一个就向前找
                    right = mid -1;
                }
            }
        }
    }
    return -1;
}

let arr = [1,3,5,7,8,8,8,10];

console.log(find(arr, 8)) // 4

(2)查找最后一个值等于给定值的元素
在（1）的基础上稍微改变下判断条件，如果当前值「处于数组的最后一个」或者「当前值后一个值不等于给定值」即可。

代码：

// 查找最后一个值等于给定值的元素
function find(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    let mid;

    while(left <= right) {
        mid = Math.floor((left + right) / 2);
        if(arr[mid] > target) {
            right = mid - 1;
        } else {
            if(arr[mid] < target) {
                left = mid + 1;
            } else {
                // 剩下都是相等的情况，在这个大条件下我们加以约束
                // 如果当前元素是「处于数组最后一个位置」或者「它后一个元素的值不等于给定值」，就符合要求
                if(mid === arr.length - 1 || arr[mid + 1] !== target) {
                    return mid;
                } else {
                    // 不是第一个就向后找
                    left = mid + 1;
                }
            }
        }
    }
    return -1;
}

let arr = [1,3,5,7,8,8,8,10];

console.log(find(arr, 8))  // 6

（3）查找第一个值大于等于给定值的元素
主体还是运用二分法，先找到「大于等于给定值的元素」区域，然后判断条件是：如果当前元素是「数组第一个」或者「它前面一个元素小于给定值」。

代码：

// 查找第一个值大于等于给定值的元素
function find(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    let mid;

    while(left <= right) {
        mid = Math.floor(( left + right) / 2);
        if(arr[mid] >= target) {
            // 这里的情况就是「值大于等于给定值」的元素
            // 判断条件是：如果当前元素是「数组第一个」或者「它前面一个元素小于给定值」
            if(mid === 0 || arr[mid - 1] < target) {
                return mid;
            } else {
                // 如果不是第一个，则向前查找
                right = mid - 1;
            }
        } else {
            left = mid + 1;
        }
    }
}

let arr = [1,3,5,7,8,8,8,10];

console.log(find(arr, 6)) // 3

（4）查找最后一个值小于等于给定值的元素
基于（3），先找到「值小于等于给定值的元素」的区域，然后判断条件是：当前元素「处于数组的最后一个位置」或者「它后一个元素的值大于给定值」即可。

代码：

// 查找最后一个值小于等于给定值的元素
function find(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    let mid;

    while(left <= right) {
        mid = Math.floor(( left + right) / 2);
        if(arr[mid] <= target) {
            // 这里的情况就是「值小于等于给定值」的元素
            // 判断条件是：如果当前元素是「数组最后一个」或者「它后面一个元素大于给定值」
            if(mid === arr.length - 1 || arr[mid + 1] > target) {
                return mid;
            } else {
                // 如果不是最后一个，则向后查找
                left = mid + 1;
            }
        } else {
            right = mid - 1;
        }
    }
}

let arr = [1,3,5,7,8,8,8,10];

console.log(find(arr, 7)) // 3