当前位置：首页 > news >正文

折半查找的实现代码：

news 来源：原创 2024/5/16 8:25:41

递归实现：

#include <iostream>

// 二分法：递归
int searchBin(int arr[], int x, int low, int high) {
	int mid;

	if(low > high)
		return -1;
	mid = (low + high) / 2;
	if(x == arr[mid])
		return mid;
	else if(x < arr[mid])
		return searchBin(arr, x, low, mid-1);
	else
		return searchBin(arr, x, mid+1, high);
}

int main(int argc, const char * argv[]) {
	// insert code here...
	int arr[] = {8, 10, 12, 15, 25, 27, 30, 38}; // 初始化数组
	int len, x, loc; // len存储数组的实际长度,x要查找的数, loc位置

	len = sizeof(arr) / sizeof(arr[0]); // 整个数组长度
	std::cout << "请输入要查找的数:\n";
	while(std::cin >> x) {
		loc = searchBin(arr, x, 0, len-1); // 调用二分查找函数
		if(loc >= 0)
			std::cout << "在数组中找到了" << x << ",在数组中是第" << (loc + 1) << "个。\n";
		else
			std::cout << "在数组中找不到" << x << std::endl;
		std::cout << "请继续输入要查找的数:\n";
	}
	return 0;
}

#include <stdio.h>
#include <stdlib.h>
#define keyType int
typedef struct {
keyType key;//查找表中每个数据元素的值
//如果需要，还可以添加其他属性
}ElemType;
typedef struct{
ElemType *elem;//存放查找表中数据元素的数组
int length;//记录查找表中数据的总数量
}SSTable;
//创建查找表
void Create(SSTable **st,int length){
(*st)=(SSTable*)malloc(sizeof(SSTable));
(*st)->length=length;
printf("输入表中的数据元素：\n");
//根据查找表中数据元素的总长度，在存储时，从数组下标为 1 的空间开始存储数据
for (int i=1; i<=length; i++) {
scanf("%d",&((*st)->elem[i].key));
}
}
//折半查找算法
int Search_Bin(SSTable *ST,keyType key){
int low=1;//初始状态 low 指针指向第一个关键字
int high=ST->length;//high 指向最后一个关键字
int mid;
while (low<=high) {
mid=(low+high)/2;//int 本身为整形，所以，mid 每次为取整的整数
if (ST->elem[mid].key==key)//如果 mid 指向的同要查找的相等，返回 mid 所指向的位置
{
return mid;
}else if(ST->elem[mid].key>key)//如果mid指向的关键字较大，则更新 high 指针的位置
{
high=mid-1;
}
//反之，则更新 low 指针的位置
else{
low=mid+1;
}
}
return 0;
}
int main(int argc, const char * argv[]) {
SSTable *st;
Create(&st, 11);
getchar();
printf("请输入查找数据的关键字：\n");
int key;
scanf("%d",&key);
int location=Search_Bin(st, key);
//如果返回值为 0，则证明查找表中未查到 key 值，
if (location==0) {
printf("查找表中无该元素");
}else{
printf("数据在查找表中的位置为：%d",location);
}
return 0;
}

以图 1 的查找表为例，运行结果为：
输入表中的数据元素：
5 13 19 21 37 56 64 75 80 88 92
请输入查找数据的关键字：
21
数据在查找表中的位置为：4
折半查找的性能分析 :是比一一对比快的，其实就是AVL树： log2(n+1)-1