折半查找

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

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

//折半查找算法
//特别注意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. 测试主函数

//测试主函数
#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;
}