算法学习记录-查找——折半查找（Binary Search）
2024-09-04 12:32:22
以前有个游戏，一方写一个数字，另一方猜这个数字。比如0-100内一个数字，看谁猜中用的次数少。
这个里面用折半思想猜会大大减少次数。
步骤：（加入数字为9）
1.因为数字的范围是0-100，所以第一次猜50（100的一半）
2.缩小范围到0-50，根据对方回应数大了，再猜25（50的一半）
3.缩小范围到0-25，对方回应数大了，再猜13
4.缩小范围到0-13，对方回应数大了，再猜7
5.缩小范围到7-13，对方回应数小了，再猜10
6.缩小范围到7-10，对方回应数大了，再猜9，中
真是比较差的情况，最差的情况这样逐次缩小到最后一个数，应该是需要猜7次。
这就是折半查找思想，非常的简单，但是有个前提，所要查找的记录序列是有序数列。
知道了思想，程序就好写了。
看图：查找7的过程
折半查找程序：
int BinSerch(myDataType *ary,int len,int val)
{
int low,mid,high;
low = ;
high = len-; while(low <= high)
{
mid = (high+low)/;
if (val == ary[mid])
{
return mid;
}
else if (val > ary[mid])
{
low = mid+;
}
else if (val < ary[mid])
{
high = mid-;
} }
return -;
}
完整代码：
#include "stdafx.h" typedef int myDataType;
//myDataType src_ary[10] = {9,1,5,8,3,7,6,0,2,4};
//myDataType src_ary[10] = {1,2,3,4,5,6,7,8,9,10};
myDataType src_ary[] = {,,,,,,,,,};
void prt_ary(myDataType *ary,int len)
{
int i=;
while(i < len)
{
printf(" %d ",ary[i++]);
}
printf("\n");
} void bubble_sort (myDataType *ary,int len)
{
int i,j;
for (i=;i<len;i++)
{
for (j=len-;j>=i;j--)
{
if (ary[j] > ary[j+])
{
myDataType temp = ary[j];
ary[j] = ary[j+];
ary[j+] = temp;
}
}
}
}
int BinSerch(myDataType *ary,int len,int val)
{
int low,mid,high;
low = ;
high = len-; while(low <= high)
{
mid = (high+low)/;
if (val == ary[mid])
{
return mid;
}
else if (val > ary[mid])
{
low = mid+;
}
else if (val < ary[mid])
{
high = mid-;
} }
return -;
} int _tmain(int argc, _TCHAR* argv[])
{
printf("before sort:\n");
prt_ary(src_ary,); bubble_sort(src_ary,); printf("after sort:\n");
prt_ary(src_ary,); int idx = BinSerch(src_ary,,);
if (- == idx)
{
printf("no value in array!\n");
}
else
{
printf("index = %d\n",idx);
} getchar();
return ;
}
测试结果：
最新文章
- 如何写出优雅的Python
- ue4 NewObject/StaticConstructObject_Internal/StaticAllocateObject/FObjectInitializer：对象创建和初始化
- css命名书写规范小结。
- urlrewrite伪静态 及多参数传递-附正则表达式语法 [轉]
- 不知道帐号密码的情况下完全重装Mac Min的OS X10.7系统
- UIWebView 获取html标题
- Linux——搭建PHP开发环境第四步：composer
- .net 中文显示乱码问题(Chinese display with messy code)
- js中prototype，__proto__，constructor之间的关系
- 【转】C++智能指针简单剖析
- 基于 HTML5 Canvas 的 3D 模型贴图问题
- TypeScript入门知识五（面向对象特性二）
- 【闲谈】应聘时要问HR的7个问题
- SQL运维
- 09-HTML-form标签
- servlet dispatcher .forward(request, response); 进入其它servlet【原】
- 强大的easygrid V7 ，可联系作者
- sencha touch list 批量选择扩展(2013-7-29)
- js验证整数，浮点数
- js array数组对象操作方法汇总