C/C++ 二分查找算法(非递归实现)_二分查找非递归算法c语言

一直都想学一下二分查找算法，奈何一直没时间；刚好最近，我的某位粉丝私信找我解答一道题目，里面要求要使用二分查找算法去实现，所以趁着这个机会，赶紧把二分查找算法学了一遍，现在记录一下自己的学习心得！

---

一、查找的的定义

首先简单了解一下查找算法的定义。

查找 又称检索或查询，是指在查找表中找出满足一定条件的结点或记录对应的操作。

查找表 在计算机中，是指被查找的数据对象是由同一类型的记录构成的集合，如顺序表，链表、二叉树和哈希表等。

查找效率 查找算法中的基本运算是通过记录的关键字与给定值进行比较，所以查找的效率同常取决于比较所花的时间，而时间取决于比较的次数。通常以关键字与给定值进行比较的记录个数的平均值来计算。

查找操作及分类
操作

1. 查找某个“特定的”数据元素是否存在在查找表中
2. 某个“特定的”数据元素的各种属性
3. 在查找表中插入一个数据元素
4. 从查找表中删除某个数据元素

分类
若对查找表只进行（1） 或（2）两种操作，则称此类查找表为静态查找表。

若在查找过程中同时插入查找表中存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类查找表为动态查找表。

即上面操作项中的1，2是静态查找表。而3，4是动态查找表。

---

二、二分查找

二分查找法实质上是不断地将有序数据集进行对半分割，并检查每个分区的中间元素。再重复根据中间数确定目标范围并递归实行对半分割，直到中间数等于待查找的值或是目标数不在搜索范围之内！

下面是二分查找的核心代码：

int BinarySearch(int *sorted, int len, int search) {
	int left = 0, right = 0, middle = 0;

	// 初始化left和right为边界值
	left = 0;
	right = len - 1;

	/* 循环查找，直到左右两个边界重合 */
	while (left <= right) {

		// 找到中间值下标
		middle = (left + right) / 2;

		/* middle索引处的值等于目标值 */
		if (sorted[middle] == search) {
			// 返回目标的索引值middle
			return middle;

			/* middle索引处的值大于目标值 */
		} else if (sorted[middle] > search) {
			// 移动到middle的左半区查找
			right = middle - 1;

			/* middle索引处的值小于目标值 */
		} else {
			// 移动到middle的右半区查找
			left = middle + 1;
		}
	}

	// 没有找到
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

通过一个while循环进行操作，判断条件是数组左边的索引值必须小于右边的的索引值。
里面的if判断都是一些简单的逻辑处理，我们以这个数组为例：int arr[] = { 1, 3, 5, 7, 9, 11, 13};

刚开始left是指向数组索引0的，也就是指向1的位置，right指向最后一个索引，也就是13的位置；
然后获取中间值middle = (left + right) / 2; ==>middle被赋值索引3，也就是7的位置；对应下方图一。

然后进行判断，通过middle获取数组的数值与查询数值(search)进行比较，如果相等，那么就是已经找到了，返回当前索引；如果中间数值大于查询数值(search)，那么查询的数值(search)就是处于左边，需要将right赋值middle的前一个位置，这也就是为什么要减一的原因，因为当前的中间值不需要再判断了，然后继续while 循环判断；
否则就是中间数值小于查询数值(search)，那么查询的数值(search)就处于右边，需要将left赋值middle的后一个位置，这就还需要加一，中间值不需要判断；对应下方图二。

然后回到while循环判断，(left <= right) --> (4 <= 6)，继续执行while循环；
获取新的中间值，（4 + 6) / 2 最后得到中间值的索引是5，然后与查找值(search)进行比较，结果相等，返回当前中间值，也就是返回对应数值的索引；对应下方图三。

到此，二分查找结束，已经找到了。

执行流程如下图：

运行截图：

---

三、测试代码

代码有两个版本，第一个版本是简单的，单一的二分查找，也就是只是支持int类型的；第二个版本就是支持其它类型的二分查找算法，有兴趣的可以看看！

第一个版本：

#include <stdlib.h>
#include <stdio.h>


/**************************************************************
 * 功能：
 *			使用while循环，使用二分查找算法找到值的索引返回
 *
 * 参数：
 *			sorted		- 待查找的数组
 *			len			- 待查找的数组元素个数
 *			search		- 查找的元素
 *
 *返回值：
 *			找到，返回在数组中的索引小标；未找到，返回-1
 ****************************************************************/
int BinarySearch(int *sorted, int len, int search) {
	int left = 0, right = 0, middle = 0;

	// 初始化left和right为边界值
	left = 0;
	right = len - 1;

	/* 循环查找，直到左右两个边界重合 */
	while (left <= right) {

		// 找到中间值下标
		middle = (left + right) / 2;

		/* middle索引处的值等于目标值 */
		if (sorted[middle] == search) {
			// 返回目标的索引值middle
			return middle;

			/* middle索引处的值大于目标值 */
		} else if (sorted[middle] > search) {
			// 移动到middle的左半区查找
			right = middle - 1;

			/* middle索引处的值小于目标值 */
		} else {
			// 移动到middle的右半区查找
			left = middle + 1;
		}
	}

	// 没有找到
	return -1;
}


/**************************************************************
 * 功能：
 *			单元测试 - 测试二分查找算法
 *
 * 参数：
 *			arr				- 待测试的数组
 *			arrLen			- 待测试的数组元素个数
 *			search			- 测试元素数组
 *			searchLen		- 测试元素数组元素个数
 *
 *返回值：
 *			无
 ****************************************************************/
void unitTest(int *arr, int arrLen, int *search, int searchLen) {
	printf("---单元测试开始---\n");

	for (int i = 0; i < searchLen; i++) {
		int index = BinarySearch(arr, arrLen, search[i]);
		printf("使用二分查找算法查找数组arr中的%d，其索引是%d\n", search[i], index);
	}
}

int main(void) {
	int arr[] = { 1, 3, 5, 7, 9, 11, 13};
	//int search[] = { -1, 0, 1, 3, 7, 11, 15 };
	int search = 11;

	int index = BinarySearch(arr, sizeof(arr) / sizeof(arr[0]), search);
	printf("使用二分查找算法查找数组arr中的%d，其索引是%d\n", search, index);

	//unitTest(arr, sizeof(arr) / sizeof(arr[0]), search, sizeof(search) / sizeof(search[0]));

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

===

第二个版本：

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string>


/***************************************************************************
 * 功能：
 *			比较两个int类型数值的大小，使用两数相减的方式(参数一减去参数二)
 *
 * 参数：	
 *			key1 - const void *类型，比较值1
 *			key2 - const void *类型，比较值2
 *
 *返回值：
 *			负数，参数二大于参数一；0，两数相等；正数，参数一大于参数二
 ***************************************************************************/
int int_compare(const void *key1, const void *key2) {
	const int *com1 = (const int *)key1;
	const int *com2 = (const int *)key2;

	return (*com1 - *com2);
}

int char_compare(const void *key1, const void *key2) {
	const char *com1 = (const char *)key1;
	const char *com2 = (const char *)key2;

	return (*com1 - *com2);
}

int str_compare(const void *key1, const void *key2) {
	const std::string *com1 = (const std::string *)key1;
	const std::string *com2 = (const std::string *)key2;

	return ((*com1).size() - (*com2).size());
}


/**************************************************************
 * 功能：
 *			使用while循环，使用二分查找算法找到值的索引返回
 *
 * 参数：
 *			sorted		- 待查找的数组
 *			len			- 待查找的数组元素个数
 *			elemSize	- 待查找数组的类型
 *			search		- 查找的元素
 *			compare		- 比较两数大小的函数指针
 *
 *返回值：
 *			找到，返回在数组中的索引小标；未找到，返回-1
 ****************************************************************/
int BinarySearch(void *sorted, int len, int elemSize, void *search, int (*compare)(const void *key1, const void *key2)) {
	int left = 0, right = 0, middle = 0;

	// 初始化left和right为边界值
	left = 0;
	right = len - 1;

	/* 循环查找，直到左右两个边界重合 */
	while (left <= right) {
		int ret = 0;

		// 找到中间值下标
		middle = (left + right) / 2;

		// 比较两个数的大小（(char *)sorted + (elemSize * middle) -> 找到middle在sorted数组位置的值）
		ret = compare((char *)sorted + (elemSize * middle), search);

		/* middle索引处的值等于目标值 */
		if (ret == 0) {
			// 返回目标的索引值middle
			return middle;

			/* middle索引处的值大于目标值 */
		} else if (ret > 0) {
			// 移动到middle的左半区查找
			right = middle - 1;

			/* middle索引处的值小于目标值 */
		} else {
			// 移动到middle的右半区查找
			left = middle + 1;
		}
	}

	// 没有找到
	return -1;
}



int main(void) {
	int arr[] = { 1, 3, 5, 7, 9, 11 };
	int search[] = { -1, 0, 1, 3, 7, 11, 15 };

	printf("\n 整数查找测试开始。。。\n");
	for (int i = 0; i < sizeof(search) / sizeof(search[0]); i++) {
		int index = BinarySearch(arr, sizeof(arr) / sizeof(arr[0]), sizeof(int), &search[i], int_compare);

		printf("使用二分查找算法查找数组arr中的%d，其索引是%d\n", search[i], index);
	}


	char arr1[] = { 'a','c','d','f','j' };
	char search1[] = { '0', 'a', 'e', 'j' , 'z' };

	printf("\n 字符查找测试开始。。。\n");
	for (int i = 0; i < sizeof(search1) / sizeof(search1[0]); i++) {
		int index = BinarySearch(arr1, sizeof(arr1) / sizeof(arr1[0]), sizeof(char), &search1[i], char_compare);

		printf("使用二分查找算法查找数组arr1中的%c，其索引是%d\n", search1[i], index);
	}


	// 还需要一些逻辑判断，目前只支持字符串的大小查找，而不是相同的查找
	//std::string arr2[] = { "abc", "1234", "qwert", "qpopo", "ffffff" };
	//std::string search2[] = { "", "abc", "qwert", "ffffff", "c" };

	//printf("\n 字符串查找测试开始。。。\n");
	//for (int i = 0; i < sizeof(search2) / sizeof(search2[0]); i++) {
	//	int index = BinarySearch(arr2, sizeof(arr2) / sizeof(arr2[0]), sizeof(std::string), &search2[i], str_compare);

	//	//printf("使用二分查找算法查找数组arr2中的%s，其索引是%d\n", search2[i], index);
	//	std::cout << "使用二分查找算法查找数组arr2中的" << search2[i] << "，其索引是" << index << std::endl;
	//}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

---

四、总结

二分查找算法，以我这种实现方式其实也是很好理解的，需要认真调试一下，多看看right和left和middle 这三个变量都有哪些变化，应该都可以看得懂！

最后需要注意：二分查找算法是基于已经排好序的数组，如果顺序是乱的，那么是查找不了的！其次，我写的这个二分查找算法是基于升序排序的，如果是降序的话，需要将 else if 的大于号改成小于号即可！如下：

		/* middle索引处的值等于目标值 */
		if (sorted[middle] == search) {
			// 返回目标的索引值middle
			return middle;

			/* middle索引处的值大于目标值 */
		} else if (sorted[middle] < search) {		// 改成小于号！！！！
			// 移动到middle的左半区查找
			right = middle - 1;

			/* middle索引处的值小于目标值 */
		} else {
			// 移动到middle的右半区查找
			left = middle + 1;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

最后，奉上我粉丝私聊我解答的题目，有兴趣的朋友可以自己做一下，我写的代码在最后面的图片中！

题目描述

在一个从大到小排列的有序序列（下标从0开始）中查找一个给定的值，并输出该值的下标。

思考：从大到小的顺序序列是否也可以应用二分查找的方法呢？

输入描述：

第一行包含一个正整数 n，表示序列中元素个数。1 <= n <= 10000。

第二行包含 n 个整数，依次给出序列的每个元素，相邻两个整数之间用单个空格隔开。请注意各个元素的绝对值不超过 10000。

第三行包含一个整数 x ，为需要查找的特定值。请注意此特定值 x 的绝对值不超过 10000。

输出描述：

若序列中存在 x，则输出 x 的下标；否则输出 -1。

输入样例1：

10
92 90 83 69 65 54 37 28 12 6 
37
输出样例1：

6
样例输入2

10
92 90 83 69 65 54 37 28 12 6 
66

样例输出2

-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35