折半查找法（迭代实现）

小甲鱼 · 发表于 2013-2-23 04:22:51

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

如果从文件中读取的数据记录的关键字是有序排列的，则可以用一种效率比较高的查找方法来查找文件的记录，这就是折半查找法，又称为二分法搜索。

折半查找的基本思想是：减小查找序列的长度，分而治之地进行关键字的查找。

折半查找的实现过程是：先确定待查找记录的所在范围，然后逐渐缩小这个范围，直到找到该记录或查找失败（查无该记录）为止。

例如有序列：1 1 2 3 5 8 13 21 34 55 89（该序列包含 11 个元素，而且关键字单调递增。），现要求查找关键字 key 为 55 的记录。

我们可以设指针 low 和 high 分别指向关键字序列的上界和下界，指针 mid 指向序列的中间位置，即 mid = (low+high)/2。

No pic you say a J8 之图1：

首先将 mid 所指向的元素与 key 进行比较，因为我们这里 key = 55，大于 8，这就说明待查找的关键字一定位于 mid 和 high 之间。于是我们执行 low = mid+1; mid = (low+high)/2;

No pic you say a J8 之图2：

然后再将 mid 所指的 34 与 key 进行比较，仍然 mid < key，所以继续执行 low = mid+1; mid = (low+high)/2;

No pic you say a J8 之图3：

接下来仍然将 mid 所指的元素与 key 进行比较，结果相等，查找成功，可喜可贺，可口可乐！

返回 mid 的指针值，程序结束！

假设我们要查找的关键字 key = 88，那么上述的查找还要继续进行下去 low = mid+1; mid = (low+high)/2;

No pic you say a J8 之图4：

完整实现代码如下：

// ********************************
// By 小甲鱼，http://www.fishc.com
// ********************************
#include <stdio.h>
int bin_search( int str[], int n, int key )
{
int low, high, mid;
low = 0;
high = n-1;
while( low <= high )
{
mid = (low+high)/2;
if( str[mid] == key )
{
return mid; // 查找成功
}
if( str[mid] < key )
{
low = mid + 1; // 在后半序列中查找
}
if( str[mid] > key )
{
high = mid - 1; // 在前半序列中查找
}
}
return -1; // 查找失败
}
int main()
{
int str[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
int n, addr;
printf("请输入待查找的关键字: ");
scanf("%d", &n);
addr = bin_search(str, 11, n);
if( -1 != addr )
{
printf("查找成功，可喜可贺，可口可乐! 关键字 %d 所在的位置是: %d\n", n, addr);
}
else
{
printf("查找失败!\n");
}
return 0;
}

复制代码

506076894 · 发表于 2013-2-23 09:06:15

这个好，强大的算法

缘缘 · 发表于 2013-2-26 19:48:59

写了个递归的：

#include<stdio.h>
#define SIZE 10
typedef int ElemType;
int refind(ElemType *data,int begin,int end,ElemType num);
int main(void){
ElemType data[SIZE]={10,20,30,40,50,60,70,80,90,100};
ElemType num;
for(int i = 0;i<SIZE;i++)
printf("%d ",data[i]);
printf("\n请输入要查找的数据:\n");
scanf("%d",&num);
int flag = refind(data,0,SIZE,num);
printf("位置为:%d\n",flag);
return 0;
}
/
//递归
int refind(ElemType *data,int begin,int end,ElemType num)
{
if(begin > end)
{
printf("没找到\n");
return -1;
}
int mid = (begin+end)/2;
if(data[mid] == num)
{
return mid;
}else if(data[mid] <= num)
return refind(data,mid+1,end,num);
else
return refind(data,begin,mid-1,num);
}

复制代码

YYB · 发表于 2013-2-27 12:56:43

我有个问题，如果mid的值不是整数怎么弄啊？比如LOW = 0 High = 9，MID =4.5 这个时候怎么办啊？str[4.5]不可以啊

小甲鱼 · 发表于 2013-2-27 14:53:56

YYB 发表于 2013-2-27 12:56

登录/注册后可看大图

我有个问题，如果mid的值不是整数怎么弄啊？比如LOW = 0 High = 9，MID =4.5 这个时候怎么办啊？str[4.5]不 ...

这里的MID是向下取整└MID┘

feitianqu · 发表于 2013-3-14 22:25:22

（）冒充下高手（）'“/"是求整不是除法哦

zhengfeilong · 发表于 2013-8-11 20:38:12

不错学习下。

轻云流风 · 发表于 2013-9-18 16:21:45

顶起，不错呀

330740120 · 发表于 2013-9-28 09:31:27

谢谢小甲鱼！存钱买视频！

铖子 · 发表于 2013-10-8 11:31:59

强烈支持楼主ing……楼下的听好了……

bare · 发表于 2013-10-9 05:43:04

数组元素再加一个就挂了？？:curse:

许许 · 发表于 2014-4-7 15:01:07

int binsearch_recursion(int a[], int low, int high, int key)
{
if(low > high)
{
return -1;
}
int mid = (low + high)/2;
if(a[mid] > key)
{
return binsearch_recursion(a, low, mid-1, key);
}
else if(a[mid] < key)
{
return binsearch_recursion(a, mid+1, high, key);
}
else
{
return mid;
}

}

沉默默 · 发表于 2014-7-25 20:37:40

# include <stdio.h>

int bin_search(int *, int, int);

int main(void)
{
int a[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};

printf("%d\n", bin_search(a, 11, 21));

return 0;
}

int bin_search(int * a, int n, int val)
{
int pos, low, hig, mid;

for (low=0, hig=n-1, mid=(low+hig) / 2; low <= hig; mid=(low+hig) / 2) {
if ( val == a[mid] )
return mid + 1;
else if ( a[mid] > val )
hig = mid - 1;
else
low = mid + 1;
}

return -1;
}

wxbmelisky · 发表于 2015-1-3 17:02:19

这个学习对我帮助很大啊好好学习

雪是梅之香 · 发表于 2015-1-19 10:29:02

现在才学习，附上我的代码：

#include <stdio.h>
#include <stdlib.h>
int find(int num[],int low,int high,int a)
{
int mid=(low+high)/2;
if(low<=high)
{
if(num[mid]==a)
{
return mid;
}
if(num[mid]>a)
{
return find(num,low,mid-1,a);
}
if(num[mid]<a)
{
return find(num,mid+1,high,a);
}
}else
{
return -1;
}
}
void main()
{
int num[]={1,1,2,3,5,8,13,21,34,55,89};
int n,result;
printf("请输入你要查找的数：");
scanf("%d",&n);
result=find(num,0,10,n);
if(result==-1)
{
printf("不存在此数");
}else
{
printf("你要找的数在第%d个位置。",result+1);
}
}

复制代码

天外飞mao · 发表于 2015-3-15 11:29:07

感谢小甲鱼

CutePrince · 发表于 2015-3-17 22:26:14

强烈支持楼主ing……
用迭代实现了一下：

#include <stdio.h>
#include <stdlib.h>
int bin_serach(int str[], int n, int key)
{
int low, mid, high;
low = 0;
high = n - 1;
while(low <= high)
{
mid = (low + high)/2;
if (str[mid] == key)
{
return mid;
}
else if (str[mid] < key)
{
low = mid + 1;
}
else {
high = mid - 1;
}
}
return -1;
}
int getAddr(int str[], int key, int low, int high)
{
if (low > high)
return -1;
int mid = (low + high) / 2;
if (key == str[mid])
return mid;
if (str[mid] < key)
{
low = mid + 1;
}
else if (str[mid] > key)
{
high = mid - 1;
}
return getAddr(str, key, low, high);
}
int main()
{
int str[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
int n, addr;
printf("请输入要查询的数字：");
scanf("%d", &n);
//addr = bin_serach(str, 11, n);
addr = getAddr(str, n, 0, 11);
if (-1 != addr)
{
printf("查找成功，查询数字%d所在的位置是：%d\n", n, addr);
}
else
{
printf("查找失败");
}
return 0;
}

复制代码

8938 · 发表于 2015-5-14 21:19:19

{:1_1:}

MozzieChow · 发表于 2015-9-14 21:51:51

//做作业

#include<stdio.h>
int bin_search(int arr[], int low, int high, int key);
void main()
{
int arr[10]={10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int key;
printf("\n请输入要查找的数据:\n");
scanf("%d", &key);
int addr = bin_search(arr, 0, 9, key);
if(addr != -1)
{
printf("key: %d, address: %d\n", key, addr);
}
else
{
printf("输入错误");
}
}
int bin_search(int arr[], int low, int high, int key)
{
int mid = (low + high)/2;
if(key == arr[mid])
{
return mid;
}
if(key <= arr[mid])
{
high = mid - 1;
bin_search(arr, low, high, key);
}
if(key >= arr[mid])
{
low = mid + 1;
bin_search(arr, low, high, key);
}
else
{
return -1;
}
}

复制代码

love_programe · 发表于 2015-10-11 14:22:11

这个算法貌似就是那个所谓的“二分法”吧！！

账号		自动登录	找回密码
密码			立即注册

[技术交流] 折半查找法（迭代实现）

马上注册，结交更多好友，享用更多功能^_^

评分

RE: 折半查找法（迭代实现）