C语言折半查找算法及代码实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了C语言折半查找算法及代码实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.折半查找的定义：

在计算机中，折半查找，也称二分搜索。它是一种在有序数组中查找某一特定元素的搜索算法。

2.折半查找的实现原理：

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

以下是折半查找和顺序遍历的算法实实现动态图

C语言折半查找算法及代码实现

3.折半查找算法优点：

折半查找法的优点是比较次数少，查找速度快，平均性能好；

其缺点是要求待查表为有序表，且插入删除困难。

因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

4.代码实现：

# include<stdio.h>
# include<string.h>
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//下标：0，1，2，3，4，5，6，7，8，9
	int k = 8;
	int left = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	int right = sz - 1;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (arr[mid] > k){
			right = mid - 1;
		}

		else if (arr[mid] < k){
		    left = mid + 1;
		}

		else{
			printf("找到了：%d\n", mid);
			break;
		}
    }

		if (left > right)//情况四：找不到
		{
			printf("找不到了\n");
		}
	return 0;
}

代码讲解：

1.通过建立左下标left与右下标right组成一个完整的范围。

2.创建关键查找数k，作为范围内要被查找的数字。

3. int mid = (left + right) / 2;这句是折半查找的核心语句，作用就是计算两边元素之和除2（为中间元素）与要查找的元素做对比，进而确定查找数的范围。

4.if (arr[mid] > k)表示情况一：求出的中间数若>要查找的数，就将右下标移位到mid的左边一位，直接消去其中一半，之后再求出左下标与更新的右下标的中间元素，更新出新的范围，再与要找元素重新进行对比。

5.else if (arr[mid] < k)表示情况二：求出的中间数若 <要查找的数，就将左下标移位到mid的右边一位，直接消去其中一半，之后再求出左下标与更新的右下标的中间元素，更新出新的范围，再与要找元素重新进行对比。

6.else表示情况三：若恰好相等，则直接跳出循环，printf打印输出。

7.if (left > right)表示情况四：找不到。

函数版：优化了一下

#include<stdio.h>
#include<String.h>
int test(int arr[], int sz, int k) {
	int left = 0;
	int right = sz - 1;
	while (left <= right)
	{
		int mid = (left + right) / 2;

		if (arr[mid] > k)
			right = mid - 1;

		else if (arr[mid] < k)
			left = mid + 1;

		else
			return mid;
	}
	if (left > right)//情况四：找不到
		return -1;
        }

int main() {
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//下标：0，1，2，3，4，5，6，7，8，9
	int k = 0;
	scanf("%d", &k);
	int sz = sizeof(arr) / sizeof(arr[0]);
	int ret = test(arr, sz, k);
	if (ret == -1) {
		printf("未找到该元素，该元素不存在！\n");
	}
	else {
		printf("找到了，该元素下标处于：%d的位置", ret);
	}
	return 0;
}

文章来源地址https://www.toymoban.com/news/detail-454409.html

到了这里，关于C语言折半查找算法及代码实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！