/* 小知识
** 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; // 没有找到
//}