C语言：二分法基本思想

C语言：二分法基本思想

假如我们要在通过代码在1 2 3 4 5 6 7 8 9 10 这几个数中找到6，那么你会怎么做？

我想必然是用6通过枚举一个个去和数据中的数进行比较吧，这样看来十分简单，我们最多比较10次就可以将6找出。

可是如果这是一个数据量庞大的数据我们应该如何找到这个数，就例如在十亿个数据中找到1787623吧，这相对来说是一个比较大的工作量了。

那么我们应该如何利用较短的时间来找到这个数。

这里我们要提到的就是二分法思想。

额，虽然面对数据量较大的数使用二分法，但是我想为了方便演示我这里就用1-10这十个数中找6来进行演示吧。

首先我们要将数据进行排序，从小到大，从大到小都可以，只要是你喜欢的。如果问为什么，解题的过程会给你答案。

我们先将第一个数字设置成first，并把1赋值给first，再将最后一个数设为last，并将它的下标赋值给last

 将中间数设成mid，mid=（first+last）/2.

所以mid=5。

当然这只是方便演示，假如这组数据是1 3 5，那么first=1，last=3，mid=2，就是他们的下标。

找出中间数之后，将他的值与目标target也就是6进行比较，你会发现6比5大，所以将5左边的数据全部抹去。

 并将first移到6的位置。

 之后继续寻找mid，mid=（first+last）/2 =(6+10)/2=8

之后我们发现6比8小，所以抹去8左边的所有数据。

 并将last移到7的位置

 然后寻找mid，发现mid=（6+7）/2=6

ok，我们找到了target。

这就是二分法的基本思想了。

#include 
int main()
{
	int str[11]={1,2,3,4,5,6,7,8,9,10};
	int first=1,last=10,mid;
	int target;                            //输入要查找的数
	scanf("%d",&target);
	while(first<=last)
	{
		mid=(first+last)/2;
		if(str[mid]>target)
			last=mid-1;
		else if(str[mid] 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5580380.html