二分查找算法详解：从基础理论到C++实现及猜数游戏应用

二分查找算法详解：从基础理论到C++实现及猜数游戏应用

引用

CSDN

1.

https://blog.csdn.net/Jeaten/article/details/107823781

二分查找，也称为折半查找，是一种高效的查找算法。它要求线性表必须是顺序存储的（数组）结构，而且顺序表中的元素是有序排列的。本文将详细介绍二分查找的原理、步骤及其在C++中的实现，并通过一个猜数游戏来进一步说明二分查找的应用。

二分查找

二分查找的基本思想是每次查找时都从中间位置开始查找。如下图所示，就是一个满足折半查找要求的存储结构：

二分查找的步骤

我们令表中元素按升序排列，则二分查找的步骤为：

1. 将中间位置的记录与给定数据进行比较，如果相等，则查找成功
2. 否则使用中间位置将表分为两个子表
3. 若给定数据大于中间位置元素，则从中间位置以后到结尾位置构成的子表中进行二分查找
4. 若给定数据小于中间位置元素，则从开始位置到中间位置构成的子表中进行二分查找
5. 重复以上过程，若找到，则查找成功；若查找到子表不存在，则给定数据不在表中

我们以在有序表 8,12,20,68,76,89,91,120,155 中查找 68 为例说明以上过程（图中 s 表示开始查找的位置，e 表示结尾查找的位置，mid 表示中间位置，我们令 mid = ⌊(s+e)/2⌋）：

1. 表长为 9，中间位置为 4，将 68 与第 4 号的数据进行比较，不相等，68 小于 76，在左边子表中进行查找：e 变为 3

2. 表长为 4，中间位置为 1，将 68 与第 1 号元素进行比较，不相等，68 大于 12，在右边子表中进行查找，s 变为 2

3. 表长为 2，中间位置为 2，将 68 与第 2 号元素进行比较，不相等，68 大于 12，在右边子表中进行查找，s 变为 3

4. 表长为 1，中间位置为 3，将 68 与第 3 号元素进行比较，相等，数据找到，返回数据位置

以上查找过程通过 4 次查找到了想要查找的数据。

二分查找的C++实现

以下是上述查找过程的C++代码实现：

#include <iostream>
using namespace std;
int s,e;
int bin_search(int arr[],int s,int e,int data){
    if(s<=e){
        int mid=(s+e)/2;
        if (arr[mid]==data){
            return mid;
        }else if(data<arr[mid]){
            e=mid-1;
            bin_search(arr,s,e,data);
        }else{
            s=mid+1;
            bin_search(arr,s,e,data);
        }
    }else{
        return -1;
    }
}
int main(){
    int arr[]={8,12,20,68,76,89,91,120,155};
    s=0,e=8;
    cout<<"place="<<bin_search(arr,s,e,68);
    return 0;
}

代码运行结果为：

place=3

猜数游戏

通过对二分查找的过程分析我们发现，对于一个数 n，我们采用二叉查找最多需要查找 ⌊log_2n⌋+1 次便可以找到该数。那么假如有一个 1000 以内的一个数，我们最多需要比较 10 次就可以找到这个数。让我们通过一个猜数游戏来体验一下：

#include <iostream>
#define Num 1000
using namespace std;
int choice,s,e,judge;
int arr[Num];
int guess(int s,int e){
    if(s<=e){
        cout<<"是"<<arr[(s+e)/2]<<"吗(1.是2.不是)？";
        cin>>judge;
        if(judge==1){
            cout<<"哈哈哈，被我猜到了吧！"<<endl;
        }else if(judge==2){
            cout<<"大了还是小了?(1.大了2.小了)";
            cin>>choice;
            switch(choice){
            case 1:
                e=(s+e)/2-1;
                guess(s,e);
                break;
            case 2:
                s=(s+e)/2+1;
                guess(s,e);
                break;
            default:
                cout<<"输入有误，继续猜啊！\n";
                guess(s,e);
            break;
        }
        }else{
            cout<<"输入有误，继续猜啊！\n";
            guess(s,e);
        }
    }else{
        cout<<"撒谎了还怎么玩游戏呢！\n"<<endl;
    }
}
int main(){
    for(int i=0;i<Num;i++)arr[i]=i+1;
    s=0,e=999;
    guess(s,e);
    return 0;
}

让我们猜个 999 玩一玩，猜的过程（运行结果）如下：

是500吗(1.是2.不是)？2
大了还是小了?(1.大了2.小了)2
是750吗(1.是2.不是)？2
大了还是小了?(1.大了2.小了)2
是875吗(1.是2.不是)？2
大了还是小了?(1.大了2.小了)2
是938吗(1.是2.不是)？2
大了还是小了?(1.大了2.小了)2
是969吗(1.是2.不是)？2
大了还是小了?(1.大了2.小了)2
是985吗(1.是2.不是)？2
大了还是小了?(1.大了2.小了)2
是993吗(1.是2.不是)？2
大了还是小了?(1.大了2.小了)2
是997吗(1.是2.不是)？2
大了还是小了?(1.大了2.小了)2
是999吗(1.是2.不是)？2
大了还是小了?(1.大了2.小了)2
是1000吗(1.是2.不是)？2
大了还是小了?(1.大了2.小了)2
撒谎了还怎么玩游戏呢！

可以看到我们在第九步猜到了。

本文原文来自CSDN