二分查找几种小小的变形

首先，二分查找的时间复杂度是O（logn）

这里不探究这个时间复杂度的原因。因为我自己还很菜，现在没有搞懂呢。

主要是想区分并理解一下关于二分查找发小小的几个变形。

再首先，下面是最基础的二分查找，就是单纯的查找一个正确值。

int binarySerach(int a[], int key)
{
    int left = 1, right = a.length;//a.length指的是数组a的长度
    while(left <= right)
    {
        int mid = (left + right) >> 2;
        if(a[mid] > key)
            right = mid - 1;
        else if(a[mid] < key)
            left = mid + 1;
        else 
            return mid;
    }
    return -1;
}

再下面的呢，就是几种小小的变形啦。

第一种：查找第一个与key相等的值，先代码，在解释。

int binarySerach(int a[], int key)
{
    int left = 1, right = a.length;//a.length指的是数组a的长度
    while(left <= right)
    {
        int mid = (left + right) >> 2;
        if(a[mid] >= key)
            right = mid - 1;
        else
            left = mid + 1;
    }
    if(a[left] == key && left <= a.length)
        return left;
    return -1;
}

其实自己举个看得过去的例子，模拟推理一遍，加上自己的总结，差不多就懂得差不多了。

比如，我举得例子就是这么一串数字：1 2 3 4 4 4 5，总共七个数。

在上面刚刚写的变形中，相当于就是要得出第一个4也就是a[4]；

left 最后是停在 a[4] 这个位置，而right 最后停在了a[3]的位置。

最后就输出所要求的数字，即left最后的值。

第二种：查找最后一个与key相等的值

int binarySerach(int a[], int key)
{
    int left = 1, right = a.length;//a.length指的是数组a的长度
    while(left <= right)
    {
        int mid = (left + right) >> 2;
        if(a[mid] <= key)
            left = mid + 1;
        else
            right = mid - 1;
    }
    if(a[right] == key && right >= 1)
        return right;
    return -1;
}

不用仔细就看会发现,和上一个没啥区别的，上一个懂了，这个也就顺理成章了。

但仔细看就会发现还是有很多细微的区别的，虽然细微，但不可或缺。我写这篇博客的时候，就因为一些小小的差别错了几次。

第三种：查找第一个大于key的元素

int binarySerach(int a[], int key)
{
    int left = 1, right = a.length;
    while(left <= right)
    {
        int mid = (left + right) >> 2;
        if(a[mid] <= key)
            left = mid + 1;
        else 
            right = mid - 1;
    }
    return left;
}

从这个开始后面的就逐渐有规律了，比如这个，跟第二种小变化其实是一样的，只不过一个是要的right值，另一个要的是left值

在有些大犇（ben）博客里呢，规律没有体现出来，情况放的有点乱，我的理解是大佬们不需要靠规律，想着就可以写出来了。

但说实话我刚会的时候靠着规律背的，时间长了就自行理解了。所以对我这种菜鸟，规律还是蛮重要的。但是呢，最好还是自己捋清楚，不能靠规律。要勤思考。嗯~ o(*￣▽￣*)o

第四种：查找最后一个小于key的元素

int binarySerach(int a[], int key)
{
    int left = 1, right = a.length;
    while(left <= right)
    {
        int mid = (right + left) >> 2;
        if(a[mid] >= key)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return right;
}

这种情况跟上面一个的简直一mu子一样。

第五种：查找最后一个小于或者等于key的元素。

int binarySerach(int a[], int key)
{
    int left = 1, right = a.length;
    while(left <= right)
    {
        int mid = (right + left) >> 2;
        if(a[mid] <= key)
            left = mid + 1;
        else right = mid - 1;
    }
    return right;
}

最后一个小于key的元素和最后一个等于key的元素为什么组成cp了呢，最直白的解释就是

都是最后一个的属性

那隐晦的解释呢，就要靠自己推一推了，举个例子，推一边，就ok了。

第六种：查找第一个大于或者等于key的元素

int binarySerach(int a[], int key)
{
    int left = 1, right = a.length;
    while(left <= right)
    {
        int mid = (left + right) >> 2;
        if(a[mid] >= key)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    return left;
}

这个就可以参考上面一个的了，虽然应该是没什么好参考的.....

就这些了，小变化应该就这些了，还有的大变化的，下次再喷。

这是我参考的博客：https://www.cnblogs.com/luoxn28/p/5767571.html