活动地址：CSDN21天学习挑战赛

✅作者简介：C/C++领域新星创作者，为C++和java奋斗中
✨个人社区：微凉秋意社区
🔥系列专栏：基础算法
📃推荐一款模拟面试、刷题神器👉注册免费刷题

🔥前言

书接上文，今天带来算法基础中的折半查找，一个相比于顺序查找效率更高的算法。这已经是基础算法专栏的第四篇文章了，感兴趣的小伙伴可以订阅专栏，学习经典算法。

折半查找算法解析

一、什么是折半查找？

折半查找又称二分查找，它要求待查找的数据元素必须是按关键字大小有序排列的。给定已排好序的n个元素s1,…,sn，现要在这n个元素中找出一特定元素x。

• 首先较容易想到使用顺序查找方法，逐个比较s1,…,sn，直至找出元素x或搜索遍整个序列后确定x不在其中。
• 显然，该方法没有很好地利用n个元素已排好序这个条件。因此，在最坏情况下，顺序查找方法需要O(n)次比较。

二、折半算法思想

假定元素序列已经由小到大排好序，将有序序列分成规模大致相等的两部分，然后取中间元素与特定查找元素x进行比较：

• 如果x等于中间元素，则算法终止；
• 如果x小于中间元素，则在序列的左半部继续查找，即在序列的左半部重复分解和治理操作；
• 否则，在序列的右半部继续查找，即在序列的右半部重复分解和治理操作。
• 二分查找算法重复利用了元素间的次序关系。

三、构造折半查找实例

创建数组并随机赋值，定义low为数组左边界high为数组右边界（数组长度-1）middle为数组长度的一半。middle=(low+high)/2，即指示中间元素；我们需要通过代码来每次折半查找我们需要的元素值。

图示：(假设想要查找15)

• 第一次二分查找，找到25
  
• 第二次二分查找，找到15
  

四、多种代码形式实现

非递归实现：

1. twoFind1()

int twoFind1(int A[], int len, int K)
{
	int low = 0, high = len - 1,middle;
	if (low > high) return -2;
	while (low <= high)//包含等于的情况
	{
		middle = (low + high) / 2;
		if (K == A[middle]) return middle;
		else if (K > A[middle]) low = middle + 1;
		else high = middle - 1;
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2. twoFind2()

int twoFind2(int A[], int len, int K)
{
	int low = 0, high = len - 1,middle;
	if (low > high) return -2;
	while (low < high)//不含等于的情况，并在最后做判断
	{
		middle = (low + high) / 2;
		if (K == A[middle]) return middle;
		else if (K > A[middle]) low = middle + 1;
		else high = middle - 1;
	}
	if (low == high && A[low] == K) return low;
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

递归实现：

int twoFind3(int A[], int k, int low, int high)
{
	int middle;
	if (low > high) return -1;//递归结束条件
	middle = (low + high) / 2;
	if (low==high && A[middle] == k) return middle;
	if (low < high) {
		if (A[middle] < k)      return  twoFind3(A, k, middle + 1, high);
		else  if(A[middle]==k)  return middle;
		else                    return  twoFind3(A, k, 0, middle - 1);
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

建议大家用纸笔配合代码执行过程来分析每一步的运行情况，这样理解起来尤为快也不容易忘记。

五、时间复杂度分析

本文算法基础之折半查找结束，期待大家的支持~