576-二分搜索算法(折半查找)

电玩女神 2022-09-11 14:21 184阅读 0赞

**如果数据序列是无序的，我们采用的是线性搜索，时间复杂度是O(n）**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16]

## 二分搜索算法(折半查找) ##

**是基于有序序列的搜索**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
**我们定义2个下标，first和last**  
![在这里插入图片描述][05fe6220f0d84e2a91d256844eab64d6.png]  
**first初始值是0，last初始值是10**  
**每次进行搜索，采用的策略是：**  
首先，计算出1个中间值：  
![在这里插入图片描述][61f5a94630eb4987bd3f35e7cba66fc4.png]  
**（0+10）/2=5**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
然后把中间的值57和我们要搜索的元素val值比较

![在这里插入图片描述][5f2716cb656b4123b14fe7434d3f37f5.png]  
**如果我们要搜索的元素的值是57，等于这个中间值，那么就找到了。**

**如果我们要搜索的元素的值大于这个中间值57**  
因为是数据有序的序列，所以我们要搜索的元素值大于这个中间值57的话，我们要搜索的元素肯定在57的右边。就不用在57的左边序列中去找。  
![在这里插入图片描述][a1e8b247fe74448eac0dad2576ec4744.png]

**如果我们要搜索的元素的值小于这个中间值57**  
因为是数据有序的序列，所以我们要搜索的元素值小于这个中间值57的话，我们要搜索的元素肯定在57的左边。就不用在57的右边序列中去找。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
然后又来计算新的middle值  
（0+4）/2=2  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
然后拿要搜索的元素的val值和这个中间值34对比

**如果这个val值大于这个中间值34**  
![在这里插入图片描述][2b6e3483b9dd4c60afebbd4153f2144d.png]  
然后计算新的middle值（3+4）/2=3  
![在这里插入图片描述][9d92e2e7788c424788a64694bb97c657.png]  
然后val值和这个中间值39比较，  
**如果这个val值小于这个中间值39，如果执行last=middle-1的话**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
**这样是错误的，因为first是起始下标，last是末尾下标。说明这次找的是34-39之间的数字，所以在序列中不存在，找不到！**

**如果这个val值小于这个中间值39**  
first=middle+1  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
**现在first和last相等了，如果找的是45，就找到了，如果比45小，或者比45大，就是表示在序列中找不到了，继续调整下标了，就是非法了，使first和last位置顺序乱套了，退出while循环，return -1了。**

**所以，我们规定：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16]

## 二分搜索算法非递归实现 ##

//二分搜索非递归实现
    int BinarySearch(int arr[], int size, int val)
    {
        
    
        int first = 0;
        int last = size - 1;
    
        while (first <= last)
        {
        
            int mid = (first + last) / 2;
            if (arr[mid] == val)
            {
        
                return mid;//找到了，返回下标 
            }
            else if (arr[mid] > val)//要找的元素的值比中间值小 
            {
        
                last = mid - 1;//到中间值的左边序列搜索 
            }
            else//要找的元素的值比中间值大 
            {
        
                first = mid + 1;//到中间值的右边序列搜索 
            }
        }
    
        return -1;//找不到，返回-1 
    }

## 二分搜索算法的时间复杂度 ##

**为什么在有序的序列里，我们要使用二分搜索，而不使用线性搜索？**  
线性搜索的时间复杂度是O(n)  
二分搜索的时间复杂度是O(logn)  
对数时间比线性时间好的多  
**为什么二分搜索的时间是对数时间呢？**  
![在这里插入图片描述][c9b98848bcb44c889e894a6ea69420ea.png]  
**它是怎么搜索的？**  
因为刚开始first是0，last是10，（0+10）/2=5，所以它先搜的是57，它拿57作为入口，如果搜索的元素的值==57，就搜到了，就走人了  
如果搜索的元素值小于57，就(0+4)/2=2,就和2号位置的34比较  
如果搜索的元素的值小于34，就(0+1)/2=1，和1号位置的25比较  
如果搜索的元素的值小于25，first和last都跑到0号位置了，就和0号位置的12比较，如果相等就找到了，如果不相等就是找不到。

如果搜索的元素的值大于34，first=3，(3+4)/2=3，和39比较，  
如果比39小，就没了，first就跑到last的后面了，  
如果比39大，first和last跑到45元素了，和45比较。  
![在这里插入图片描述][ac153246d4ea44469938f12e0ea907ab.png]

如果搜索的元素值大于57，first跑到6号位置，(6+10)/2=8，比较元素82，  
如果搜索的元素比82小，last跑到7号位置，(6+7)/2=6，和63比较  
如果比63小，就没有了，first跑到last的后面了，结束了。  
如果比63大，first和last跑到7号位置，和78比较  
如果比82大，first跑到9号位置，(9+10)/2=9，可以和96比较  
比96小就没了，比96大，还可以和100比较

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
**二分搜索相当于就是从这棵二叉树的根节点开始时，沿着某一个路径进行搜索的过程，最多搜到叶子节点上。**  
**这是一棵BST树，二叉搜索树**  
**左孩子的值小于父节点的值，父节点的值小于右孩子的值。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]  
**二分搜索在每一层只会搜索1个节点**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]  
**所以，**![在这里插入图片描述][5b1b715b0ec94a6ea3997fff0b876906.png]  
**二叉树的层数和对应的节点数的关系：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]  
**n就是节点总个数**

![在这里插入图片描述][79682f2289ef4223b5faf93823d8dd60.png]  
**我们可以把1省略掉，因为这个1相当于根节点，根节点肯定是最先走的节点，我们就省略掉。  
树的层数：L**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]  
![在这里插入图片描述][3fc404076e914b949784eb43eed19556.png]

## 二分搜索的高效率应用场景 ##

**如果我们有100w个数据，是有序的，最多搜log以2为底的100w**  
![在这里插入图片描述][8291954b79e4487faaf97435b51da1f2.png]  
![在这里插入图片描述][74dd1000fc254dd284c4e2ad8f185bc1.png]  
**最多搜索20次就可以了！**![在这里插入图片描述][e59eece05c5946eb93eb472a3f08ebe3.png]  
**在有序的1000w个数据中搜索，最多搜索24次就可以了！**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]

## 递归复习图解 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 12]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 13]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 14]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 15]  
递的过程是在不断缩小问题的规模，缩小问题规模的过程中，不同数据规模之间，它们求解的结果是有关系的，  
递不是无穷无尽的递，递一次就要开辟一次空间，栈的空间是比较小的，所以对于大数据处理，最好使用非递归方法处理 ，递的过程，一定会有递的规模，数据规模小到问题的结果是已知的  
递到最后最小问题规模的结果是已知的，然后把每一层的结果一直向上归回去，最后n问题规模的解就解出来了

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 16]  
![在这里插入图片描述][acac20363de947fe9cf669b0f4b84ebb.png]  
**求n的阶乘：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 17]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 18]

## 二分搜索算法的递归实现 ##

![在这里插入图片描述][80b773ff338d469c8eb43ab4194b5f27.png]  
![在这里插入图片描述][14196ef3872c478a957aa4142aa10c1f.png]  
**第一步：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 19]  
**第二步：**  
![在这里插入图片描述][3478a0a6ab7d4e838bbc7c3eb638b6a9.png]  
**第三步：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 20]  
**如果找到了，就把mid一直返回去  
如果找不到，就把-1一直返回去**

#include <iostream>
    using namespace std;
    
    //二分搜索递归代码
    int BinarySearch(int arr[], int i, int j, int val)
    {
        
        if (i > j)//递归结束的条件 
            return -1;
    
        int mid = (i + j) / 2;
        if (arr[mid] == val)
        {
        
            return mid;
        }
        else if (arr[mid] > val)
        {
        
            return BinarySearch(arr, i, mid - 1, val);
        }
        else
        {
        
            return BinarySearch(arr, mid + 1, j, val);
        }
    }
    
    
    //二分搜索非递归实现
    int BinarySearch(int arr[], int size, int val)
    {
        
        return BinarySearch(arr, 0, size - 1, val);
    }
    
    int main()
    {
        
        int arr[] = {
         12, 25, 34, 39, 45, 57, 63, 78, 82, 96, 100 };
        int size = sizeof arr / sizeof arr[0];
        cout << BinarySearch(arr, size, 39) << endl;
        cout << BinarySearch(arr, size, 45) << endl;
        cout << BinarySearch(arr, size, 12) << endl;
        cout << BinarySearch(arr, size, 64) << endl;
    
        return 0;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 21]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d7a9bf08eddf4c3e8d329d0e34dab9a3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/29a69e2fd870426e8e70e9aac8f58eab.png
[05fe6220f0d84e2a91d256844eab64d6.png]: /images/20220828/8ef6122167dd4be29098bae0be751b71.png
[61f5a94630eb4987bd3f35e7cba66fc4.png]: /images/20220828/bb78f828b3f049cfbdf26778c6e885c6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/e70426dfed944fb4bccc95b97c4df048.png
[5f2716cb656b4123b14fe7434d3f37f5.png]: /images/20220828/a9c705dc47774743a14e54e2d0dc6b67.png
[a1e8b247fe74448eac0dad2576ec4744.png]: /images/20220828/f27ec9c6bf394f1093b948b167beabd5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/aac32fda4cfd4fb5850dea058d9570e6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/0138e04b09dc4dd28d7d4853decaeb87.png
[2b6e3483b9dd4c60afebbd4153f2144d.png]: /images/20220828/ca3e496bf85a4e3da1f6a7f2d96c4ef4.png
[9d92e2e7788c424788a64694bb97c657.png]: /images/20220828/0b95a87661004adaa41126badeef746c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/f1135de146ec49898c8184e450a3e639.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/dff012f7723b414991b3a910d58d4a35.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/ef178688e44d4c57a67e525809c4cd21.png
[c9b98848bcb44c889e894a6ea69420ea.png]: /images/20220828/857a477d775b423ebeb459acdd958633.png
[ac153246d4ea44469938f12e0ea907ab.png]: /images/20220828/0a32800b7f62439b8b4f5c14d9834e1f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/347deb62e2af4b009fd36e00297ac775.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/1637401100704fcca157f1eeb6f9ea98.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/6bac49b1d6934175ac8744763020c121.png
[5b1b715b0ec94a6ea3997fff0b876906.png]: /images/20220828/40787618390e44e4968f0d60a8605991.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/0ae1073aa9b84814bd0ce0594a80af2b.png
[79682f2289ef4223b5faf93823d8dd60.png]: /images/20220828/c0091509499d40cbbcb62c81766cf88b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/70f1b811e6e54d7d921ac3e708d089ba.png
[3fc404076e914b949784eb43eed19556.png]: /images/20220828/72f24be9491c4880985f5fae4da1afad.png
[8291954b79e4487faaf97435b51da1f2.png]: /images/20220828/a3485fa52bd6489a91abf473673a4e5e.png
[74dd1000fc254dd284c4e2ad8f185bc1.png]: /images/20220828/27be06506f9b4a3187f08bf2f53c01de.png
[e59eece05c5946eb93eb472a3f08ebe3.png]: /images/20220828/f04b410201c5437ca038ccd1ed402aeb.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/759cdb512376420abc50dfdfdf965bad.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]: /images/20220828/4bb66d12a720467ea32e365256421c9c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 12]: /images/20220828/6d4a2af8e610451d97725c8f7304b7dc.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 13]: /images/20220828/25148e0184c344619b757afb33efa673.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 14]: /images/20220828/c797047f01a045de96d98d6f55653e6e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 15]: /images/20220828/7cf827406c95463dbedf46508da3729f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/2b5c8e093c42431dba5702799ee448cd.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 16]: /images/20220828/64a7d36b480342e886bfda4f1a3757aa.png
[acac20363de947fe9cf669b0f4b84ebb.png]: /images/20220828/58067b3743bb43d7a24f8e59bc800420.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 17]: /images/20220828/4c7ce8f7597945cc898cdf0a45191b33.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 18]: /images/20220828/28e42e13a23d4c8b93be8c1f5774f2ae.png
[80b773ff338d469c8eb43ab4194b5f27.png]: /images/20220828/0e97e669b33b44a18aed9225a1c1152b.png
[14196ef3872c478a957aa4142aa10c1f.png]: /images/20220828/c80c0b021aea40dca5ef208a0c9cae6c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 19]: /images/20220828/eb4829016f354e65bee807b855531fb5.png
[3478a0a6ab7d4e838bbc7c3eb638b6a9.png]: /images/20220828/ac7d891149214c8491e5353ef6edcf76.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 20]: /images/20220828/02188cd2278b41c29298b5d99a4b6881.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 21]: /images/20220828/56cdfd54309f4e988b719a6c31977abc.png