二分查找就该这样学

向右看齐 2023-03-14 13:16 14阅读 0赞

**点击关注上方“五分钟学算法”，**

**设为“置顶或星标”，第一时间送达干货。**

![format_png][]

转自景禹

小禹禹，你们好呀！从今天开始景禹就要开始给大家分享查找和排序算法，有没有很鸡冻。查找算法在日常的考试、面试中都极为常见。

## 基础 ##

静态查找（Static Search）：数据集合稳定，不需要添加，删除元素的查找操作。

动态查找（Dynamic Search）：在数据集合中进行查找的过程中，需要同时添加或删除元素的查找操作。

关键字（key）：数据元素（或记录）中某个数据项的值，用它可以唯一的标识（识别）一个数据元素（或记录）。

对于静态查找来说，我们可以采用用线性表结构组织数据，这样可以使用顺序查找算法，如果我们再对关键字进行排序，则可以使用折半查找算法或斐波那契查找算法等来提高查找的效率。

对于动态查找来说，我们则可以考虑使用二叉排序树的查找技术，另外我们还可以使用散列表结构来解决一些查找问题，这些查找算法景禹都会一点儿一点儿介绍给小禹禹的。

其实本质上查找算法一般分为两类：

*  顺序查找（Sequential Search）：将顺序遍历链表或数组，并检查每个元素。（比如线性查找）
 *  区间查找（Interval Search）：这类算法是专门为查找排序的数据结构而设计的。这些类型的查找算法比线性查找有效得多，因为它们反复检查查找空间的中心并不断将查找空间缩减。（比如二分查找）

景禹今天主要给小禹禹分享一下线性查找和二分查找，其中线性查找的的思想简单，景禹就不一步一步给大家分析演示了，不过提供了动画演示，不理解的小禹禹可以对照着看一下。

## 线性查找 ##

顺序查找（Sequential Search）又叫线性查找（Linear Search），是最基本的查找技术，它的查找过程为：从表中的第一个（或者最后一个）记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功。如果查找了所有的记录仍然找不到与给定值相等的关键字，则查找不成功。

### 动画演示 ###

### 实现代码 ###

从前往后进行遍历查找：

#include <stdio.h>
    
    int search(int arr[], int n, int x) 
    {
      int i;
      for (i = 0; i < n; i++)
        if (arr[i] == x)
          return i;
      return -1;
    }
    
    int main(void) 
    {
      int arr[] = { 5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92 };
      int x = 64;
      int n = sizeof(arr) / sizeof(arr[0]);
      int result = search(arr, n, x);
      (result == -1) ? printf("Element is not present in array")
            : printf("Element is present at index %d",
                  result);
      return 0;
    }

从后往前进行遍历查找：

int search(int arr[], int n, int x) 
    {
      int i = n-1;
      while(arr[i] != x){
            i--;
        }
        if(i >= 0)
        return i;
        return -1;
    }

### 时间复杂度 ###

线性查找的时间复杂度为

## 二分查找 ##

二分查找又叫做折半查找，其查找过程为：先确定待查记录所在的范围（区间），然后逐步缩小范围知道找到或者找不到该记录为止。注意二分查找是在有序表上进行的，且二分查找也是分治思想的很好例证。之前景禹在谈递归与分治时就曾介绍过二分查找，今日再详细探讨一下。

![format_png 1][]我们以上面的有序数组，查找关键字21的数据元素为例进行说明。

第一步：设置一个指向有序数组第一个元素 5 的low指针，和一个指向有序数组的最后一个元素 92 的high指针。

![format_png 2][]

第二步：计算 low 指针与 high 指针的中点，并用 mid 指针保存。low 的初值为0， high 的初值为11，则  ，即指向记录56.

![format_png 3][]

第三步：将给定值21与mid指针指向的值56进行比较，21 < 56，说明待查找元素21若存在，必在区间 \[low,mid-1\] 的范围内，则令 `high = mid - 1 = 5- 1 = 4.`

![format_png 4][]

第四步：重新计算 mid 的值，`mid =⌊(0+4)/2⌋=2.`

![format_png 5][]

第五步：将给定值21与mid指向的值19进行比较，21 > 19，说明待查找元素21若存在，必在区间 \[mid+1,high\] 的范围内，则令 low = mid + 1 = 2+ 1 = 3.

![format_png 6][]

第六步：重新计算mid 的值，`mid =⌊(3+4)/2⌋=3.`

![format_png 7][]

第七步：将给定值21与mid指向的值21进行比较，发现相等，查找成功。

从上面的例子可见，折半查找过程以处于区间中间位置mid记录的值和给定值比较，若相等，则查找成功，若不相等，则缩小范围，直至新的区间中间位置mid记录的值等于给定值或者查找区间的大小小于零时（表示查找不成功）为止。

### 二分查找递归实现 ###

#include <stdio.h>
    
    int binarySearch(int arr[], int low, int high, int x)
    {
      if (high >= low) {
        int mid = low + (high - low) / 2;
    
        //判断mid指向值是否等于指定值x
        if (arr[mid] == x)
          return mid;
    
        //如果mid指向的元素的值大于指定值x，
        //则递归地遍历区间[l,mid-1]
        if (arr[mid] > x)
          return binarySearch(arr, low, mid - 1, x);
    
        //如果mid指向的元素的值小于指定值x，
        //则递归地遍历区间[mid+1, high]
        return binarySearch(arr, mid + 1, high, x);
      }
    
      //查找的元素不存在返回-1
      return -1;
    }
    
    int main(void)
    {
      int arr[] = { 5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92 };
      int n = sizeof(arr) / sizeof(arr[0]);
      int x = 64;
      int result = binarySearch(arr, 0, n - 1, x);
      (result == -1) ? printf("Element is not present in array")
            : printf("Element is present at index %d",
                  result);
      return 0;
    }

### 二分查找迭代实现 ###

int binarySearch(int arr[], int low, int high, int x)
    {
      while(low <= high){
        int mid = low + (high - low) / 2;
    
        if (arr[mid] == x)
          return mid;
        if (arr[mid] < x){
          low = mid + 1;
        }
        else{
          high = mid - 1;
        }
      }
      return -1;
    }

### 时间复杂度 ###

为了清晰地计算二分查找的时间复杂度，我们将例子中的数组转化为一颗二叉树。

![format_png 8][]

查找21仅需要比较2次，查找37仅需要比较3次。显而易见，对于一个有序数组而言，查找某个元素的判断次数最多也就是上面的一颗判断树的深度，而具有n个结点的判定树的深度为，所以在一个有序数组中查找一个元素的时间复杂度为级别。

## 二分查找的应用 ##

LeetCode 704. 二分查找 (Binary Search)

小禹禹赶紧去力扣提交一下，体验一波成功感吧，哈哈！！！景禹为了让小禹禹对二分查找理解更深刻，我们再来看一道题目。

### 题目描述 ###

> 统计一个数字在排序数组中出现的次数。
> 
> 例如输入排序数组\[1, 2, 3, 3, 3, 3, 4, 5\]和数字3，由于3在这个数组中出现了4次，因此输出4。

### 示例 ###

> 示例 1：
> 
> 输入：\[1, 2, 3, 3, 3, 3, 4, 5\] , 3
> 
> 输出：4 解释：数组中总共有4个3

### 题解： ###

第一种方式当然特别简单，只需要写一个循环，遍历数组一遍，统计出排序数组中重复数字的个数。时间复杂度为.

另一种方式就是我们今天所学习的二分查找了，怎么办？

小禹禹：嗯？？？还可以用二分查找，也就意味着时间复杂度降到.

景禹：的确如此，那就让我们快乐的开始吧。

首先我们应该注意到输入的是一个 **排序数组** ，面试只要提到有序数组这种，小禹禹一定要有警惕性，面试官可不想只看到的解法。

二分查找本身是用于查找数组中是否存在一个元素，若存在在返回数组的下标，若不存在，则返回-1。而现在我们我们要统计的是数组中重复元素出现的次数，有没有可能对二分查找进行修改后做到呢？答案是肯定的。

![format_png 9][]

我们只需要确定出第一个3的位置以及最后一个3的位置，然后将两个位置相减并加一，就是重复元素的个数。

**如何计算第一个重复元素的位置？**

第一步：依然是设置一个指向第一个元素的low指针，和指向最后一个元素的high指针

![format_png 10][]

第二步：计算指针 `mid =⌊(0+7)/2⌋=3.`

![format_png 11][]第三步：比较mid 指向的元素 3 与重复元素的大小，如果 mid 指向的元素 **大于等于** 重复元素，则令 `high = mid - 1`. 否则，令 `low = mid + 1` . 这里是是大于等于，故 `high = 3 - 1 = 2`.

![format_png 12][]

第四步：计算指针 `mid =⌊(0+2)/2⌋=1.`

![format_png 13][]

第五步：比较mid 指向的元素 2 与重复元素 3 的大小， 2 < 3，则 `low = mid + 1 = 2`

![format_png 14][]

第六步：计算 `mid =⌊(2+2)/2⌋=2.`

![format_png 15][]

第七步：比较mid 指向的元素 3 与重复元素 3 的大小， 3 <= 3，则 `high = mid - 1 = 1` 此时 `low > high` ,退出循环并返回指针 low 的值 2。

![format_png 16][]

**如何获得最后一个重复元素的位置？**

与上面寻找第一个重复元素的位置一样，我们只需要将判断条件进行更改，也就是说，当mid指向的值 **小于等于** 重复元素，则 `low = mid + 1` ，否则，令 `high = mid - 1` .

通俗来讲，我们寻找第一个重复元素，将high指针向low 靠近，寻找最后一个元素，将low指针向high靠近。

我们一起来看代码吧！超级简单。

计算第一个重复元素的位置：

int binarySearch_start(int arr[], int low, int high, int x)
    {
      while(low <= high){
        int mid = low + (high - low) / 2;
    
        if (arr[mid] < x){
          low = mid + 1;
        }
        else{
          high = mid - 1;
        }
      }
      return low;
    }

计算最后一个重复元素的位置：

int binarySearch_end(int arr[], int low, int high, int x)
    {
      while(low <= high){
        int mid = low + (high - low) / 2;
    
        if (arr[mid] <= x){
          low = mid + 1;
        }
        else{
          high = mid - 1;
        }
      }
      return low;
    }

至于重复元素的个数则为：最后一个重复元素的位置 - 最后一个重复元素的位置 + 1.

当然我们可以有一种更简洁的思路，那就是找到第一个元素的位置，然后找出最后一个元素的位置的下一个位置，然后进行相减即可得到重复元素的个数：

#include <stdio.h>
    
    int binarySearch(int arr[], int low, int high, int x)
    {
      while(low <= high){
        int mid = low + (high - low) / 2;
    
        if (arr[mid] < x){
          low = mid + 1;
        }
        else{
          high = mid - 1;
        }
      }
      return low;
    }
    
    int main(void)
    {
      int arr[] = { 1,2,3,4,4,4,4,4,4,4,6,6,7,8,9,10 };
      int n = sizeof(arr) / sizeof(arr[0]);
      int x = 4;
      int start = binarySearch(arr, 0, n - 1, x);
      int end = binarySearch(arr, 0, n -1 ,x+1);
      int result = end - start;
      printf("The number of Repeating element is %d",result);
      return 0;
    }

景禹今天就写到这里啦，希望小禹禹有所收获，一切顺利，学习愉快，原创不易，素质三连是对景禹的最大鼓励！一起加油呀~~

--------------------

### **推荐阅读** ###

• [C++是如何从代码到游戏的？][C]• [告诉你一个学习编程的诀窍（建议收藏）][Link 1]• [自学编程的八大误区！克服它！][Link 2]• [新手如何有效的刷算法题（LeetCode）][LeetCode]• [10款VS Code插件神器，第7款超级实用！][10_VS Code_7]• [在拼多多上班，是一种什么样的体验？我tm心态崩了呀！][tm]• [写给小白，从零开始拥有一个酷炫上线的网站！][Link 3]

--------------------

欢迎关注我的公众号“**五分钟学算法**”，如果喜欢，麻烦点一下“**在看**”~

![format_png 17][]

[format_png]: /images/20230312/748f62fe664944ee92197b5fbde95127.png
[format_png 1]: /images/20230312/9c69a1a65996467d9d94bcc932c68d33.png
[format_png 2]: /images/20230312/f5e425c0d92c45d19b58136f827e3a23.png
[format_png 3]: /images/20230312/dcf7f85bd5944dc6922ebf973e561a66.png
[format_png 4]: /images/20230312/f9a1d1dc779f48ad8bd08460ce49f2c8.png
[format_png 5]: /images/20230312/43c16d2bf5054a118acd519b6bfc2c94.png
[format_png 6]: /images/20230312/217888e45db74f2f9f97237a1f619213.png
[format_png 7]: /images/20230312/b2fd27470c9d4afb970281d499744502.png
[format_png 8]: /images/20230312/454ad475d5ed4ea5a4f204a0a17621c4.png
[format_png 9]: /images/20230312/a242afc85eba416f856985bed0d7f38a.png
[format_png 10]: /images/20230312/84c6284973534f20973b19593a37ed03.png
[format_png 11]: /images/20230312/09b32b28db894305a25f89d1cb76537a.png
[format_png 12]: /images/20230312/feea3fe503234f829e4217a81243f65b.png
[format_png 13]: /images/20230312/41c5fd1b417b486d8b00d74a9eff274c.png
[format_png 14]: /images/20230312/1958301654184cd3a2502df2bc315279.png
[format_png 15]: /images/20230312/2b7af1962f174a4d8c6cfd1c82ef50f9.png
[format_png 16]: /images/20230312/681aa99e14f74f56b8323258a86c3274.png
[C]: https://blog.csdn.net/kexuanxiu1163/article/details/105897849
[Link 1]: https://blog.csdn.net/kexuanxiu1163/article/details/105911378
[Link 2]: https://blog.csdn.net/kexuanxiu1163/article/details/105742893
[LeetCode]: https://blog.csdn.net/kexuanxiu1163/article/details/105742896
[10_VS Code_7]: https://blog.csdn.net/kexuanxiu1163/article/details/105721292
[tm]: https://blog.csdn.net/kexuanxiu1163/article/details/105697118
[Link 3]: https://blog.csdn.net/kexuanxiu1163/article/details/105648532
[format_png 17]: /images/20230312/88e21f52321a4fd7afc35dfa1483894c.png