零基础入门学习C语言007讲：数组（3）

﹏ヽ暗。殇╰゛Y 2022-04-24 20:52 227阅读 0赞

# **二维数组程序举例---二分法举例** #

例   假设在数组a中的数据是按由小到大顺序排列的：

\-12  0  6  16  23  56  80  100  110  115，从键盘上输入一个数，判定该数是否在数组中，若在，输出所在序号。

**第一步**：设low、mid和high三个变量，分别指示数列中的起始元素、中间元素与最后一个元素位置, 其初始值为low=0,high=9,mid=4，判断mid指示的数是否为所求，mid指示的数是23，不是要找的80，须继续进行查找。

![20190429201902731.png][]

第二步：确定新的查找区间。因为80大于23，所以查找范围可以缩小为23后面的数，新的查找区间为\[56    80    100    110    115 \]，low,mid,high分别指向新区间的开始、中间与最后一个数。实际上high不变，将low（low=mid+1）指向56,mid （mid=(low+high)/2）指向100,还不是要找的80，仍须继续查找。

![20190429201938663.png][]

第三步：上一步中，所找数80比mid指示的100小，可知新的查找区间为\[56  80\]，low不变，mid与high的值作相应修改。mid指示的数为56，还要继续查找。

![20190429202030425.png][]

第四步：根据上一步的结果，80大于mid指示的数56，可确定新的查找区间为\[80\]，此时，low与high都指向80，mid亦指向80，即找到了80，到此为止，查找过程完成。

![20190429202044496.png][]

**注意：**若在查找过程中，出现low > high的情况，则说明，序列中没有该数，亦结束查找过程。

#include <stdio.h>
    #define M 10
    #include<stdio.h>
    
    void main()
    {
    	static int a[M] = { -12, 0, 6, 16, 23, 56, 80, 100, 110, 115 };
    //一个程序在编译运行时，普通变量是存放在栈，我们还会学习堆，而这个static会使得变量存放在data。
    //我们整个内存主要分为四大区：CODE、DATA、STACK、HEAP。
    	int n, low, mid, high, found;
    	low = 0;
    	high = M - 1;
    	found = 0;
    	printf("Input a number to be searched:");
    	scanf("%d", &n);
    	//以上进行一系列预处理……
    	while (low <= high)
    	{
    		mid = (low + high) / 2;    	
    		if (n == a[mid])
    		{
    			found = 1;     
    			break;
    		}/*找到，结束循环*/     	
    		else if (n > a[mid])
    		{
    			low = mid + 1;
    		}
    		else
    		{
    			high = mid - 1;
    		}
    	} 
    	if (found == 1)
    	{
    		printf("The index of %d is %d", n, mid);
    	} 
    	else
    	{
    		printf("There is not  %d", n);
    	}	
    }

[20190429201902731.png]: /images/20220212/374599dec78a465ab2b21560ddb5e5c2.png
[20190429201938663.png]: /images/20220212/1cb55d1bb0d14f518a156e3182256fe7.png
[20190429202030425.png]: /images/20220212/2d1e595df4194f67a6e22254bc0526a8.png
[20190429202044496.png]: /images/20220212/436875654680410e8b62ecc81b6039a6.png