欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

折半查找算法的实现

程序员文章站 2024-03-20 18:07:16
...

添加链接描述
今天学习了折半查找算法 本想着找一篇代码实现,在实现过程中遇到了很多的错误.这里说明一下
首先我将代码直接复制过来 就报出了一下吓人的错误:

test3.cpp:5:1: error: stray ‘\302’ in program
     keyType key;//查找表中每个数据元素的值
 ^
test3.cpp:5:1: error: stray ‘\240’ in program
test3.cpp:5:1: error: stray ‘\302’ in program
test3.cpp:5:1: error: stray ‘\240’ in program
test3.cpp:6:1: error: stray ‘\302’ in program
     //如果需要,还可以添加其他属性


于是在网上找了一下原因

可能是复制过来的时候有些无法解析的非法ascii码字符,解决方案是

od -c *.cpp  
去查看哪里有 非法字符把它们删掉即可
最简单的方法是将这段代码复制到本文编辑器中,然后在复制过来  就可以运行了

然后在运行过程中,可以编译也能生成可执行文件,但是在运行的时候一直报出

输入表中的数据元素:
5 13 19 21 37 56 64 75 80 88 92
段错误 (核心已转储)

于是我对上面的代码做出了一部分调整 这样就可以运行了
下面附上代码

#include <stdio.h>
#include <stdlib.h>
#define keyType int
#define MAX 20
typedef struct {
    keyType key;//查找表中每个数据元素的值
    //如果需要,还可以添加其他属性
}ElemType;
typedef struct{
    ElemType elem[MAX];//存放查找表中数据元素的数组
    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;
}

输出结果:

输入表中的数据元素:
5 13 19 21 37 56 64 75 80 88 92
请输入查找数据的关键字:
21
数据在查找表中的位置为:4

后期也找了一篇可以直接运行的代码 但是没有上面的代码灵活性大

# include <stdio.h>
# include <stdlib.h>
# include <assert.h>
 
/*
*	函数名称:BinarySearch
*
*	函数功能:二分查找排好序的数组中的某个元素
*
*	入口参数:pArr, key, len
*
*	出口参数:mid
*
*	返回类型:int
*/
 
int BinarySearch(int * pArr, int key, int len)
{
	int left = 0;
	int right = len - 1;
	int mid = 0;
 
	assert(NULL != pArr);
	
	while (left <= right)
	{
		mid = (left & right) + ((left ^ right) >> 1);
 
		if (pArr[mid] == key)
		{
			return mid;
		}
		else if (pArr[mid] > key)
			{
				right = mid - 1;	
			}
			else
			{
				left = mid + 1;
			}
	}
 
	return -1;
}
 
int main(void)
{
	int arr[] = {1,2,3,4,5,6,7,8,9,10};
	int key = 7;
	int len = sizeof(arr) / sizeof(int);
	int ret = BinarySearch(arr, key, len);
	
	if (-1 == ret)
	{
		printf("没找到%d!\n", key);
	}
	else
	{
		printf("找到了%d,它的下标是%d\n", key, ret);
	}
 
	return 0;
}

```这里可以直接运行