1、二分查找介绍

二分查找(Binary search)也称折半查找,是一种效率较高的查找方法。但是,二分查找要求线性表中的记录必须按关键码有序,并且必须采用顺序存储

2、二分查找演示

下面是二分查找与顺序查找的演示图对比:

可以看出 二分查找 在查找数字 37 时只需3次,而 顺序查找 在查找37时需要12次。 

3、二分查找原理

二分查找算法的原理如下:
        1. 设置查找区间:low = 0;high= n;
        2. 若查找区间[low, high]不存在,则查找失败;否则转步骤3
        3. 取中间位mid = (low + high) / 2;比较 target 与 arr[mid],有以下三种情况:
                3.1 若 target < arr[mid],则high = mid - 1;查找在左半区间进行,转步骤2;
                3.2 若 target > arr[mid],则low = mid + 1;查找在右半区间进行,转步骤2;
                3.3 若 target = arr[mid],则查找成功,返回 mid 值;

4、二分查找性能

时间复杂度
       二分查找最好时间复杂度
                最好情况下只需要进行1次比较就能找到目标元素
        二分查找最坏时间复杂度
                最坏情况就是查找不到目标元素,所需的时间复杂度可借助该序列的二叉树(二分查找判定树)形式进行分析:
                        序列[5, 10, 22, 29, 43, 57, 58, 61, 73, 77, 81]可以构建成下图所示的二叉树

                 具有n个结点的二分查找树的深度为,因此,查找成功时,所进行的关键码比较次数至多为。而查找失败时和目标元素进行比较的次数最多也不超过树的深度,因此最坏时间复杂度时
        二分查找平均时间复杂度
                由二分查找的平均查找长度可知:

ASL = \sum_{i = 1}^{n}p_{i}c_{i}=\frac{1}{n}\sum_{j=1}^{k}j\times 2^{j-1}=\frac{1}{n}\(1\times 2^{0}+2\times 2^{1}+...+k\times 2^{k-1})

        平均时间复杂度是

5、二分查找C++代码实现

5.1、二分查找非递归实现:

int BinarySearch(int arr[], int len, int target) {
	int low = 0;
	int high = len;
	int mid = 0;
	while (low <= high) {
		mid = (low + high) / 2;
		if (target < arr[mid]) high = mid - 1;
		else if (target > arr[mid]) low = mid + 1;
		else return mid;
	}
	return -1;
}

完整代码:

#include<iostream>
using namespace std;

int BinarySearch(int arr[], int len, int target) {
	int low = 0;
	int high = len;
	int mid = 0;
	while (low <= high) {
		mid = (low + high) / 2;
		if (target < arr[mid]) high = mid - 1;
		else if (target > arr[mid]) low = mid + 1;
		else return mid;
	}
	return -1;
}
int main() {
	int array[] = { 7,14,18,21,23,29,31,5,38,42,46,49,52 };
	int arrayLen = sizeof(array) / sizeof(array[0]);
	int index = BinarySearch(array, arrayLen, 52);
	if (index != -1) {
		cout << "查找" << array[index] << "成功";
	}
	else {
		cout << "查找失败";
	}
	return 0;
}

 5.2、二分查找递归实现:

int BinarySearch(int arr[], int low, int high, int target) {
	if (low > high)return -1;
	else {
		int mid = (low + high) / 2;
		if (target < arr[mid]) return BinarySearch(arr, low, mid - 1, target);
		else if (target > arr[mid]) return BinarySearch(arr, mid + 1, high, target);
		else return mid;
	}
}

完整代码:

#include<iostream>
using namespace std;

int BinarySearch(int arr[], int low, int high, int target) {
	if (low > high)return -1;
	else {
		int mid = (low + high) / 2;
		if (target < arr[mid]) return BinarySearch(arr, low, mid - 1, target);
		else if (target > arr[mid]) return BinarySearch(arr, mid + 1, high, target);
		else return mid;
	}
}
int main() {
	int array[] = { 7,14,18,21,23,29,31,5,38,42,46,49,52 };
	int arrayLen = sizeof(array) / sizeof(array[0]);
	int index = BinarySearch(array, 0, arrayLen, 52);
	if (index != -1) {
		cout << "查找" << array[index] << "成功";
	}
	else {
		cout << "查找失败";
	}
	return 0;
}

6、参考链接

参考链接
参考链接
参考链接​​​​​​​
参考链接

Logo

为开发者提供学习成长、分享交流、生态实践、资源工具等服务,帮助开发者快速成长。

更多推荐