数据结构与算法之经典算法《二分查找》

今天药忘吃喽~ 2023-09-26 15:56 135阅读 0赞

![b18a6a52a0584f02953615b79c712c4e.gif][]

> **文章目录**
> 
> 引入
> 
> 一、二分查找的简单解释
> 
> 二、二分查找的思路解析
> 
> 1、二分查找的思路描述
> 
> 2、二分查找的代码实现
> 
> 总结

## 引入 ##

> 这里我给大家一个有序数组，要在这个数组中找到指定的元素。
> 
> 例：在下面数组中找到‘7’，并返回其下标。

int arr[] = { 0,1,2,3,4,5,6,7,8,9,10 };

> 方法会有很多，我的第一反应的想法如下：

#include<stdio.h>
    int main()
    {
    	int i = 0;
    	int arr[] = { 0,1,2,3,4,5,6,7,8,9,10 };
    	int k = 7;
    	for (i = 0; i < 11; i++)
    	{
    		if (arr[i] == k)
    			printf("找到了，下标是%d\n", i);
    	}
    	if (i == 11)
    		printf("没找到");
        return 0;
    }

> 上面代码的思路就是遍历数组，一个一个查找。当然这种方法是肯定可行的。但是，当这个数组有较多数据时，我们就会发先，查找起来效率很低。因为这里是一个有序的数组，这就给了我们很大的发挥空间，因而我们就可以使用二分查找（折半查找），可大大提高效率。
> 
> 接下来我给大家仔细解释一下二分查找。

## 一、二分查找的简单解释 ##

> 二分查找也算是一个非常简单的算法了，也是我们必须要掌握的一个算法。那么二分查找是什么呢？二分查找的思路是什么呢？
> 
> 二分查找又叫折半查找，是应用在一个***有序数组***中的一个高效率查找的方法。这里要注意的是，二分查找前提是必须是有序的数组。

## 二、二分查找的思路解析 ##

### 1、二分查找的思路描述 ###

> 因为是有序的数组，我们就可以直接用数组中间的元素来和你要查找的元素进行比较。如果中间的元素比你要查找的元素大，我们就可以直接舍去数组的后半部分，定位到数组前半部分。同样，如果中间的元素比你要查找的元素小，我们就可以直接舍去数组的前半部分，定位到数组后半部分。在剩下的数据中我们再次重复上面的操作，当中间的元素等于你要查找的元素时，就找到了。我们发现，每次查找都会舍去现有的一半数据，相对遍历数组查找大大提高了效率。

> 中间元素的查找方法就是**mid=（左元素下标 +右元素下标）/2。**如果中间的元素比你要查找的元素大，我们怎么来到前半部分呢？很简单，**左素下标不用变，我们只需要将右元素的下标改成中间元素下标减去一即可**。如果中间的元素比你要查找的元素小，我们怎么来到半后部分呢？**右元素下标不用变，左下标变成中间元素下标加一。**

![148afb7068f348099d4bb721ac2991e4.png][]

> 那要是查找的元素不存在呢？就上面的图我们来解释一下。假设我们要找的元素是6.5， 当进行到第三步时，我们就会只剩下‘7’这个元素。这时左下标是等于右下标的。但是中间的元素和要查找的元素并不相等，其实这是中间元素还是本身，但还需要再次查找比较，中间的元素比你要查找的元素大，右元素下标要减一。我发现，左元素下标大于了右元素下标，因为是有序的，这就意味着找不到了。
> 
> 下面我们结合着代码综合理解一下。

### 2、二分查找的代码实现 ###

#include<stdio.h>
    int main()
    {
    	int i = 0, k = 0;
    	int arr[] = { 0,1,2,3,4,5,6,7,8,9,10 };
    	int left = 0;
    	int right = sizeof(arr) / sizeof(arr[0])-1;
    	printf("请输入你要查找的数:>");
    	scanf("%d", &k);
    	while (left<=right)
    	{
    		int mid = (left + right) / 2;
    		if (arr[mid] > k)
    		{
    			right = mid - 1;
    		}
    		else if (arr[mid] < k)
    		{
    			left = mid + 1;
    		}
    		else
    		{
    			printf("找到了，下标是%d", mid);
    			break;
    		}
    	}
    	if (left > right)
    		printf("没找到");
    	return 0;
    }

> 上面的代码中，要查找的数改成自己输入了。但是二分查找的思路是没变的。

## 总结 ##

> 1.  二分查找应用在有序数组中；
> 2.  重点理解二分查找的思路；
> 3.  掌握二分查找代码的实现。

[b18a6a52a0584f02953615b79c712c4e.gif]: https://img-blog.csdnimg.cn/b18a6a52a0584f02953615b79c712c4e.gif
[148afb7068f348099d4bb721ac2991e4.png]: https://img-blog.csdnimg.cn/148afb7068f348099d4bb721ac2991e4.png