目录

一、折半查找（二分查找）

二、插值查找

总代码

---

一、折半查找（二分查找）

原理：一次次折半，不断向着查找值的位置靠近 。

适用场景：有序（必须）

流程：开始时，min标志首，max标志尾，medium=(min+max)/2。然后即可开始查找，判断str[medium]和要查找的值是否相等：1、相等：min = medium+1         2、不相等：max=medium-1  。

 

 

//折半查找（注：前提是有序序列）
int Binary_Search(char ch)
{
	int min = 0, max = strlen(str)-1;
	int medium;
	while (min <= max)
	{
		medium = (max + min) / 2;		//取中值
		if (ch == str[medium])
			return medium;
		else if (ch > str[medium])
			min = medium+1;				//进入右半边（medium位置已查找过，跳过）
		else
			max = medium-1;				//进入左半边（medium位置已查找过，跳过）
	}

	return -1;
}

二、插值查找

按比例查找到最接近的位置。选取一段的比例（如：(min+小半段)*总），有序且数据分布均匀时，可以更快的定位。

适用场景：有序（必须），数值分布均匀，线性增长。

//插值查找（比例查找）
int Insert_Search(char ch)
{
	int medium, min = 0, max = strlen(str) - 1;
	while (min <= max)
	{
		//取比例
		medium = min + (ch - str[min]) / (str[max] - str[min]) * (max - min);	
		if (ch == str[medium])
			return medium;
		else if (ch > str[medium])
			min = medium + 1;				//进入右半边（medium位置已查找过，跳过）
		else
			max = medium - 1;				//进入左半边（medium位置已查找过，跳过）
	}

	return -1;
}

总代码

//有序表查找（折半查找、插值查找）
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string>

char str[20];

//输入
char Input()
{
	char ch = ' ';
	printf("请输入一串数组：\n");
	for (int i = 0; i < 20 && ch != '\n'; i++)
	{
		scanf("%c", &ch);
		str[i] = ch;
	}
	printf("请输入您想要查找的字符：");
	scanf("%c", &ch);
	return ch;
}

//折半查找（注：前提是有序序列）
int Binary_Search(char key)
{
	int min = 0, max = strlen(str)-1, mid;
	while (min <= max)
	{
		mid = (max + min) / 2;		//取中值
		if (key == str[mid])
			return mid;
		else if (key > str[mid])
			min = mid+1;				//进入右半边（mid位置已查找过，跳过）
		else
			max = mid-1;				//进入左半边（mid位置已查找过，跳过）
	}

	return -1;
}

//插值查找（比例查找）
int Insert_Search(char key)
{
	int mid, min = 0, max = strlen(str) - 1;
	while (min <= max)
	{
		//取比例
		mid = min + (key - str[min]) / (str[max] - str[min]) * (max - min);
		if (key == str[mid])
			return mid;
		else if (key > str[mid])
			min = mid + 1;			//进入右半边（mid位置已查找过，跳过）
		else
			max = mid - 1;			//进入左半边（mid位置已查找过，跳过）
	}

	return -1;
}


int main()
{
	char ch;
	ch = Input();				//输入

	printf("折半查找(二分查找)结果： %d\n", Binary_Search(ch));		//折半查找

	printf("插值查找结果：%d\n", Insert_Search(ch));					//插值查找
	
	return 0;
}