二分查找（变体）

今天写4种二分查找的变体分别是
查找第一个值等于给定值的元素
查找最后一个值等于给定值的元素
查找第一个值大于等于给定值的元素
查找最后一个值小于等于给定值的元素
虽说是是4种，但是原理上第一个和第二个、第三个和第四个原理都是相同的，这里我只会写第一种和第三种的代码。

查找第一个值等于给定值的元素

int searchFirstEqual(int arr[], int length, int value) {
    int low, middle, high;
    low = 0;
    high = length - 1;

    while(low <= high) {
        middle = low + ((high - low) >> 1);
        if(arr[middle] == value) {
            if ((0 == middle) || (value != arr[middle - 1]))
            {
                return middle;
            } else {
                high = middle - 1;
            }
        } else if(arr[middle] > value) {
            high = middle - 1;
        } else {
            low = middle + 1;
        }
    }

    return -1;
}

重点

如果当前值等于要查找的元素这时我们就判断它是否是第一个元素或者它前一个元素的值不等于给定值，满足上述条件它就是第一个值等于给定值的元素。
如果它之前有元素且值等于给定值这时我们就将 high 更新为 middle - 1；

查找第一个值大于等于给定值的元素

int searchFirstLessEqual(int arr[], int length, int value) {
    int low, middle, high;
    low = 0;
    high = length - 1;

    while(low <= high) {
        middle = low + ((high - low) >> 1);
        if (arr[middle] >= value)
        {
            if (0 == middle || arr[middle - 1] < value)
            {
                return middle;
            } else {
                high = middle - 1;
            }
        } else {
            low = middle + 1;
        }
    }

    return -1;
}

重点

如果当前元素大于等于给定值这时我们就判断它是否是第一个元素或者它前一个元素的值不大于等于给定值，满足上述条件就直接返回当前元素的下标。
如果它之前有元素且大于等于给定值，这时我们就更新 high = middle - 1；

变体的二分查找就写到这了

二分查找的代码看上去很简单，但是写的时候容易忽略细节。

都看到这了，点个赞再走啊~