实现折半查找的算法

63 阅读 0 评论 42 点赞

我是靠谱客的博主超级方盒，最近开发中收集的这篇文章主要介绍实现折半查找的算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

/**
* 实验题目:
* 实现折半查找的算法
* 实验目的:
* 领会折半查找的过程和算法设计
* 实验内容:
* 设计程序，输出在顺序表(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)中采用
* 折半查找方法查找关键字9的过程
*
*/

#include <stdio.h>

#define MAX_LEN (100)

typedef int key_type; // 定义关键字类型为int
typedef char info_type;

typedef struct
{
key_type key; // 关键字项
info_type data; // 其他数据项,类型为InfoType
}rec_type; // 声明查找顺序表元素类型

/*-------------------创建顺序表---------------------*/
void create_list(rec_type records[], key_type keys[], int n)
{
int i;

for(i = 0; i < n; i++) // records[0...n - 1]存放排序记录
records[i].key = keys[i];
}

/*-------------------输出顺序表---------------------*/
void disp_list(rec_type records[], int n)
{
int i;

for(i = 0; i < n; i++)
printf("%d ", records[i].key);
printf("n");
}

/**
* 利用折半查找方法在顺序表records(含有n个元素)
* 中查找关键字为key的记录位置
*/
static int bin_search(rec_type records[], int n, key_type key) // 折半查找算法
{
int low = 0;
int high = n - 1;
int mid;
int cnt = 0;

while(low <= high)
{
mid = (low + high) / 2;
printf(" 第%d次比较:在[%d,%d]中比较元素records[%d]:%dn", ++cnt, low, high, mid, records[mid].key);
if(records[mid].key == key) // 查找成功返回
return mid + 1;
if(records[mid].key > key) // 继续在records[low...mid - 1]中查找(左半部分)
high = mid - 1;
else // 继续在records[mid + 1...high]中查找(右半部分)
low = mid + 1;
}

return -1;
}

int main(void)
{
rec_type records[MAX_LEN];
int i;
int n = 10;
key_type key = 9;
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

create_list(records, a, n); // 建立顺序表
printf("关键字序列:");
disp_list(records, n);
printf("查找%d的比较过程如下:n", key);
i = bin_search(records, n, key);
if(i != -1)
printf("元素%d的位置是%dn", key, i);
else
printf("元素%d不在表中n", key);

return 0;
}

测试结果:

关键字序列:1 2 3 4 5 6 7 8 9 10
查找9的比较过程如下:
第1次比较:在[0,9]中比较元素records[4]:5
第2次比较:在[5,9]中比较元素records[7]:8
第3次比较:在[8,9]中比较元素records[8]:9
元素9的位置是9