折半查找法(11.15总结)

一.折半查找法原理

折半查找法的主要思想是将一个有序数列分为两部分,然后将待查找的数与中间值比较,从而确定待查找数存在的范围.通过逐步比较缩小范围,最终确定所查找的数

二.折半查找法步骤

1.定义中间值mid

2.定义左右两端的下标left right,如果待查找值大于中间值,将左端下标移至mid+1的位置(根据实际数列的排序方式)

3.如果待查找值小于中间值,将右端下标移至mid-1的位置

4.重复2.3过程,最终确定位置

三.图解

(借用一下别人的图)

如图,要查找的数为7,将7与该数列的中间数比较

很明显7大于中间数,7在中间数的右端,那么下标需要向右移动

第二次查找如下,7明显小于中间数,这时下标便需要向左移动

通过循环进行这个过程,最终确定待查找数的位置

四.代码实现

#include<stdio.h>
int main()
{
	int a[15]={15,14,13,12,11,10,9,8,7,6,5,4,3,2,1},middle,x,big,small;
	printf("输入要查找的数字:");
	scanf("%d",&x);
	left=0;
	right=14;					//left为左区间 right为右区间
	while(left<=right)
	{
		middle=(left+right)/2;
		
		
		
	    if(a[middle]<x)
				right=middle-1;				
		else if(a[middle]>x)					//缩小区间范围
				left=middle+1;		
		if(a[middle]==x)
		{
			printf("查找的数字为第%d个数字",middle+1);
			break;
		}
	}
	return 0;
}