Question

求二分法查找演示C语言源代码

【问题描述】 用箭头表示指针，模拟出二分法查找的指针变化过程。
【要 求】 给定一组数据。可以动态地显示二分法查找的过程。用到函数：setcolor(WHITE)－画颜色，line(x1,y1,x2,y2)－画直线;，bar(x1,y1,x2,y2)－画矩形，settextstyle(0,0,2)－字体大小，outtextxy(x,y,变量或常量)－输出内容; initgraph(&gd,&gm,"c:\\tc") －tc所在目录的路径，setfillstyle(SOLID_FILL,0)－每次演示的时候先将下面显示的文字给去处掉，等等。

Answer 1

二分法查找算法：

1. 主要思想是：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段 中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。

2. 时间复杂度:  O(log2n)。

3. C语言源代码(小例子）

  search函数即为核心代码：递归查找

#include<stdio.h>
int search(int *a, int num, int low, int high)
{
	int mid =(low + high)/2;
	if(low<=high)
	{
		if(num < a[mid])
			return search(a, num, low, mid-1); //加return
		if(num > a[mid])
			return search(a, num, mid+1, high);//加return
		if(num==a[mid])                     
			return 1;
	}
	else
		return 0;
}
int main(){
	int a[11] = {0, 1, 2, 3, 4, 5, 9, 11, 12, 13, 15};
	if(search(a, 11, 0, 10)==1)
		printf("success!!");
	else 
		printf("failed!!");
}

Answer 2

#include <stdio.h>
//递归算法
int recurbinary(int *a,int key,int low,int high)
{
int mid;
if(low > high)
return -1;
mid = (low + high)/2;
if(a[mid] == key) return mid;
else if(a[mid] > key)
return recurbinary(a,key,low,mid -1);
else
return recurbinary(a,key,mid + 1,high);
}
//非递归算法[1]
int binary( int *a, int key, int n )
{
int left = 0, right = n - 1, mid = 0;
mid = ( left + right ) / 2;
while( left < right && a[mid] != key )
{
if( a[mid] < key )
left = mid + 1;
else if( a[mid] > key )
right = mid - 1;
mid = ( left + right ) / 2;
}
if( a[mid] == key )
return mid;
return -1;
}
int main()
{
int a[] = {1,2,3,4,5,6,7,8,9,12,13,45,67,89,99,101,111,123,134,565,677};
int b[] = { 677, 1, 7, 11, 67 };
int i;
for( i=0; i<sizeof(b)/sizeof(b[0]); i++ )
{
printf( "%d\n", recurbinary(a,99,0,sizeof(a)/sizeof(a[0])-1) );
//printf( "%d\n", binary( a, 45, sizeof(a)/sizeof(a[0])));
}
return 0;
}