查找算法：二分查找

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

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

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

二分查找算法的原理如下：
        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 值；

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

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

        平均时间复杂度是。

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
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;
}

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
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;
}

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