折半查找算法（BinarySearch）-Toy模板网

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

折半查找算法（BinarySearch）

1、BinarySearch算法的描述

查找算法是一种在数字列表中确定目标元素所在位置的算法。假设给定一个目标元素 11 和一个包含元素 11 的数字列表（例如 10, 11, 12，13，14, 15, 16, 17, 18, 19, 20），然后在该数字列表中找到目标元素的位置。

折半查找算法也叫做对分查找和二分查找。折半查找算法适合用于有序的数字列表，无序的数字列表适合顺序查找（SequentialSearch）。折半查找算法逻辑是从一个数字列表的中间元素开始查找，这将能够判别出目标元素在列表的前半部分还是在列表的后半部分；如果在前半部分，就不需要查找后半部分；如果在后半部分，就不需要查找前半部分。这将使得算法的性能更好和效率更高。

重复这个过程直到找到目标元素或者确定目标元素不在这个数字列表中。如果找到该目标元素，则输出目标元素的位置；如果没有找到，则返回-1。当然，返回值可以随意设定，不一定是-1，其目的是为了更好的人机交互。

2、用图示描述BinarySearch算法

注：图想法源于机械工业出版社出版的《计算机科学导论》（P163）,作者是【美】贝赫鲁兹-佛罗赞

上图给出了如何在 11 个元素的数字列表中找到目标元素 11，其中定义了 3 个数组下标变量left、right 和 mid 。图中银灰色区域是在折半查找过程中被忽略的那一半元素。下面描述折半查找算法的详细步骤。

（1）开始时，left 为 1，right 为10。计算中间位置 mid (( left +right)/2), (0 + 10)/2 = 5, 即中间位置为5，其元素为 15 。现在比较目标元素 11 和在中间位置元素 15 , 11 < 15 ,所以忽略后半部分，即 15（包含 15）以后的所有元素。

（2）将 right 移到 mid 前面，即位置 4。计算第二个一半的中间位置 mid，（0 + 4）/ 2 = 2，即中间位置为 2，其元素为 12。现在比较目标元素 11 和在中间位置元素 12 ，11 < 12 ，所以忽略12（包含12）以后的元素。

（3）将 right 移到 mid 前面，即位置 1。计算第三个一半的中间位置 mid，如上图所示，只剩余两个元素，没有中间位置，但是根据程序可以计算出其“相对中间位置”，mid 计算的结果指向哪个位置，那个位置就是“相对中间位置”。（0 + 1）/ 2 = 0,因为数组下标是整形，所以计算结果是0，即中间位置为 0，其元素为 10。现在比较目标元素 11 和在中间位置元素 10, 11 > 10 , 所以忽略10（包含 10）以前的元素。

（4）因为 11 > 10 , 所以将 left 移到 mid 后面，即位置 1。按照程序计算第四个一半的中间位置 mid ，（1 + 1）/ 2 = 1 ; 即中间位置为 1 ，其元素为 12 。现在比较目标元素 11 和在中间位置元素 11，11 = 11 , 即找到目标元素，此时算法结束。

折半查找算法要设计成：找到目标元素或者目标元素不在算法中停止。从这个算法中可以看出：当目标元素不在列表中时，left 的值大于right 的值，即数组左下标大于数组右下标，这在数组中是完全不可能的，所以这反常的条件就是结束算法的终止条件。

3、用代码描述BinarySearch算法

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

//查找的目标元素
#define X 15

//函数声明
int BinarySearch(int* arr, int sz, int x);

int main()
{
	//将需要查找目标元素的数字列表存入数组
	int arr[] = { 10,11,12,13,14,15,16,17,18,19,20 };

	//求数组元素的个数
	int sz = sizeof(arr) / sizeof(arr[0]);

	//定义查找的目标元素
	int x = X;

	//数组、数组元素个数和目标元素
	int position = BinarySearch(arr, sz, x);

	//输出目标元素的位置
	if (position != -1)
	{
		printf("目标元素在第 %d 个位置", position);
	}
	else
	{
		printf("没有找到");
	}

	return 0;
}	

int BinarySearch(int* arr, int sz, int x)
{
	//左下标
	int left = 0;

	//右下标
	int right = sz;

	while (left <= right)
	{
		//中间元素下标
		int mid = (left + right) / 2;

		if (x > arr[mid])
		{
			left = mid + 1;
		}
		else if (x < arr[mid])
		{
			right = mid - 1;
		}
		else
		{
			return mid + 1;
		}
	}

	//没有找到
	return -1;
}

关键代码解释：

return mid + 1;

因为数组下标是从 0 开始的，下标比真正的元素位置错位 1，所以在找到目标元素后，将其数组下标加 1 就是该目标元素真正的位置。

4、总结

这篇文章写了BinarySearch算法的文字描述、图示描述和代码描述。在这里为了方便实现此算法，只输入了 11 个没有重复且有序的正整数。算法一般情况下具有通用性，所以这个BinarySearch 算法可以查找 n 个整数。各位看官，也可以拷贝代码试试输入更多的整数（正整数，0和负整数），看看这个算法能不能对目标元素准确查找。

各位看官，也可以根据此算法，自己写一写查找具有重复数字的逻辑代码。有啥好的想法我们可以评论区互相交流呀，今天的分享总结就到这里了，我们下期再见！！！文章来源地址https://www.toymoban.com/news/detail-768909.html

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