现在的位置: 首页 > 综合 > 正文

折半查找算法

2012年11月23日 ⁄ 综合 ⁄ 共 1619字 ⁄ 字号 评论关闭
/*  小知识
**  vs2008中三个常用的快捷键
**      1. ctrl+k+ctrl+c   注释
**      2. ctrl+k+ctrl+u  取消注释
**      3. ctrl+k+ctrl+f   对齐代码
*/
/* 折半查找算法
** 问题描述
**     从一串从小到大排好序的数中找出自己需要的数 searchnum
**     折半查找需要完成两个子任务:
**           1. 判断序列中是否还有没有查到的整数,需找大查找结束的边界,在下面
**                边界为 left >= right
**           2. 比较需要查找的数 searchnum 与 list[middle]
*/
#include <stdio.h>
#include <stdlib.h>
#define COMPARE(x,y)  (( (x)<(y) )?  -1 : ( (x) == (y)) ? 0 :1 )

// 折半查找函数原型声明
int binsearch( int list [], int searchnum, int left, int right);   //  prototype
/*
**  比较函数
**        int compare(int x, int y)
**           {
**                 if(x<y) return -1;
**                 else if( x==y) return 0;
**                 else return 1;
**           }
**   宏命令  COMPARE(x,y)  (( (x)<(y) )?  -1 : ( (x) == (y)) ? 0 :1 )
*/
int main()
{
	// 人为给定一个排好的序列,方便问题的描述
	int list[10]={1,4,6,9,20,32,44,53,98,100};
	int left_n=0;
	int right_n=9;
	int search;
	int result;
	printf("enter the number you need to find :   ");
	scanf("%d",&search);
	printf("\n");
	// 通过返回的结果对查找进行判断,找到就返回下标索引
	result=binsearch(list,search,left_n,right_n);    
	if(-1==result)
		printf("Can't find the number you need!  \n");
	else
		printf("Got it! the number index is [ %d ]  \n",result);
	printf("\n");
	system("pause");
	return 0;
}

/*  折半查找算法之普通算法
**     int binsearch( int list [], int searchnum, int left, int right);
*/
 int binsearch( int list [], int searchnum, int left, int right)
 {
	 int mid;
	while(left<=right)
	 {
		 mid=(left+right)/2;
		 switch(COMPARE(list[mid],searchnum))
		 {
		 case -1:
			 left=mid+1; break;
		 case 0:
			 return mid;   //  找到
		 case 1:
			 right=mid-1;
		 }
	 }
	 return -1;  //  没有找到
 }

 /*  折半查找算法之递归算法
**     int binsearch( int list [], int searchnum, int left, int right);
*/

 //int binsearch( int list [], int searchnum, int left, int right)
 //{
	// int mid;
	//if(left<=right)
	// {
	//	 mid=(left+right)/2;
	//	 switch(COMPARE(list[mid],searchnum))
	//	 {
	//	 case -1:
	//		 return binsearch(list,searchnum,mid+1,right);  // 递归实现右半部分
	//	 case 0:
	//		 return mid;   //  找到
	//	 case 1:
	//		 return binsearch(list,searchnum,left,mid-1);    // 递归实现左半部分
	//	 }
	// }
	// return -1;  //  没有找到
 //}

抱歉!评论已关闭.