折半查找

《数据结构(C语言版)》学习笔记:折半查找算法(p5)

1. 折半查找算法C语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//折半查找算法
//特别注意switch中的break不能漏掉
int binsearch(int list[], int searchnum, int left, int right)
{
int midnum;
while (left <= right)
{
midnum = (left + right) / 2;
switch (compare(list[midnum], searchnum))
{
case -1:left = midnum + 1;
break;//注意:break不能掉
case 0:return midnum;
case 1:right = midnum - 1;
}
}
return -1;
}
int compare(int a, int b)
{
if (a>b) return 1;
else if (a == b) return 0;
else return -1;
}


2. 测试主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//测试主函数
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAX_SIZE 1000
void select_swap(int *a, int *b);//实现代码见上一篇:选择排序算法
void sort(int list[], int n);//实现代码见上一篇:选择排序算法
int compare(int a, int b);
int binsearch(int list[], int searchnum, int left, int right);
int main()
{
int num;
int list[MAX_SIZE];
printf("Enter the number of numbers to generate:");
scanf_s("%d", &num);
if (num<1 || num>MAX_SIZE)
{
fprintf(stderr, "Improper value of n.\n");
exit(1);
}
for (int i = 0; i < num; i++)
{
list[i] = rand() % 1000;
printf("%d ", list[i]);
}
sort(list, num);
printf("\nsorted array:\n");
for (int i = 0; i < num; i++)
printf("%d ", list[i]);
printf("\ninput searchnum:");
int searchnum;
scanf_s("%d", &searchnum);
int indice = binsearch(list, searchnum, 0, num-1);
indice>-1 ? printf("%d is in the sorted list:list[%d]=%d\n", searchnum,indice, searchnum) : printf("%d is not in the sorted list.\n", searchnum);
system("pause");
return 0;
}


本文标题:折半查找

文章作者:wuxubj

发布时间:2016年06月28日 - 21:06

最后更新:2017年05月03日 - 10:05

原始链接:http://www.wuxubj.cn/2016/06/binary-search/

许可协议: Attribution-NonCommercial 4.0 转载请保留原文链接及作者。

扫二维码
扫一扫,用手机访问本站

扫一扫,用手机访问本站