8-二分查找

二分查找和拓展篇

引言：如何在最短时间内，在有序数据中，找出目标数据？

顺序查找？随机查找？不不不，那就是伟大的二分查找思想。今天我们来讨论二分查找的思想和其它4种拓展思维。最后还会介绍一种伟大的数据结构，也是用了二分查找的思想，它就是跳表。

• 二分查找
• 基于二分查找的其它思想
• 跳表(redis)的简介

1.二分查找

find1.jpg

例子：假设我们根据上图数据，已经排好序，找数据19的位置。如何用二分思想？
1.我们先设置low,high,mid三个标记，low总是指向范围的下界，high指向上界,mid就是(low+high)/2的位置
2.第一次查找，mid=(0+9)/2=4;对应数据是27，比我们要查找的19大，证明19只可能出现在low--mid区间，此时更改high=mid-1,low不变。low=0,high=3,mid=(3+0)/2=1
3.第二次查找,mid对应的数据是11,比目标值要小，证明目标只可能出现在后半段，所以继续修改low=mid+1=2,,high不变还是3，mid=(2+3)/2=2
4.第三次查找，mid对应的数据就是19.成功找到。

方法总结：
1.设置三变量low,high,mid，分别标记数据的下界和上界和中间位置。
2.每次取出中间位置的数据对比目标数据，如果大于目标数据，证明数据只可能出现在前半段，只修改high,进而mid也被改变；如果小于目标数据，证明数据只可能出现在前后段，只修改low,进而mid也被改变。
3.重复操作二，直到循环退出

/*           二分查找           */
int Search_Binary1(int *arr,int len, int num)
{
    int low, high ,mid;
    low = 0, high = len - 1;
    mid = (low + high) / 2;
    //循环结束的条件是low>high
    while (low <= high)
    {
        if (arr[mid] == num)
        {
            return mid;
        }
        else if (arr[mid] < num)
        {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    return -1;
}

2.二分查找的四种变种版本

• 查找数据中第一个等于目标值的位置
• 查找数据中最后一个等于目标值的位置
• 查找数据中第一个大于等于目标值的位置
• 查找数据中第一个小于等于目标值的位置

我们假设上面的数据都是有序的。

变体一：查找数据中第一个等于目标值的位置

int Search_Binary2(int *arr, int len, int num)
{
    int low, high, mid;
    low = 0, high = len - 1;
    mid = (low + high) / 2;
    while (low <= high)
    {
        if (arr[mid] == num)
        {
            if (mid == 0 || arr[mid - 1] != num)
            {
                return mid;
            }
            else
            {
                high = mid - 1;
            }
        }
        else if (arr[mid] < num)
        {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    return -1;
}

为了讲解方便，我们直接分析代码。对比普通的二分查找，发现，基本还是一样的，不一样的就是在if (arr[mid] == num)这一句代码，正常情况下，我们是直接返回找到的这个位置，但是在变体一中，我们需要继续判断这个数据是不是第一个我们要找的数据。
看代码，很容易分析出，如果此时的mid等于0了，肯定是第一个出现的，还有一种情况，就是看找到的数据前面有没有等于自己的数据，没有也就是ok的，因为，数据是有序的，前面不等于自己，自己就是唯一第一个出现的了。
否则证明我们要找的数据不是第一个出现的，它在前面，因此，将high修改位mid-1.

变体二：查找数据中最后一个等于目标值的位置

int Search_Binary3(int *arr, int len, int num)
{
    int low, high, mid;
    low = 0, high = len - 1;
    mid = (low + high) / 2;
    while (low <= high)
    {
        if (arr[mid] == num)
        {
            if (mid == len - 1 || arr[mid + 1] != num)
            {
                return mid;
            }
            else {
                low = mid + 1;
            }
        }
        else if (arr[mid] < num)
        {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    return -1;
}

理解了第一个变体，后面的都十分so easy! 继续在找到的数据中判断，看找打的数距如果是最后一个位置或者，它的后面数据不等于它，那它就是我们要找的最后一个数据
反之，证明要找的数据在后面，修改low=mid+1

变体三：查找数据中第一个大于等于目标值的位置

int Search_Binary4(int *arr, int len, int num)
{
    int low, high, mid;
    low = 0, high = len - 1;
    mid = (low + high) / 2;
    while (low <= high)
    {
        
        if (arr[mid] >= num)
        {
            if (mid == 0 || arr[mid - 1] < num)
            {
                return mid;
            }
            else {
                high = mid - 1;
            }
        }
        else {
            high = mid - 1;
        }
    }
    return -1;
}

变体四：查找数据中最后一个小于等于目标值的位置

int Search_Binary5(int *arr, int len, int num)
{
    int low, high, mid;
    low = 0, high = len - 1;
    mid = (low + high) / 2;
    while (low <= high)
    {

        if (arr[mid] <= num)
        {
            if (mid == len-1 || arr[mid +1] > num)
            {
                return mid;
            }
            else {
                low = mid + 1;
            }
        }
        else {
            high = mid - 1;
        }
    }
    return -1;
}

二分查找是基于顺序查找的升级，效率十分快。但是确定也十分明显，就是需要数据有序。它的时间复杂度是0(log n).

3.跳表(redis)

我们知道二分查找利用了数组的下标随机访问的特性，快速定位查找元素，但是如果我们的数据保存在链表？链表定位某个节点需要逐个遍历。那么一位大佬设计了一种牛逼的不行的数据结构，跳表

基于跳表，我略微查阅了资料，看起来还是挺复杂，大佬们有兴趣可以去学习学习。

获取完整代码

我分别用C，C++，JAVA三种主流语言编写了完整代码，请大家指导批正，一起学习。

点击查看