[C++知识库]二分法C++版

二分法的学习总结

紧接着之前分享的git bisect知识点，本次呢，我们来学习一下二分法；
笔者能力有限，还望各位读者不吝赐教，万分感谢！
提到二分法便想起来对中折绳子，这些数据储存在数组中并且已经排好序，我们不必一个个去查找符合要求的选项，现在我们看一下二分法如何实现的吧！
前提：
已知数据已经排好序，并且存储在数组中；
首先判断数组是否为空或是数组个数是否符合要求（大于0），满足这些要求的话，我们便可以得到数组的第一个元素low及最后一个元素high，紧接着判断中间元素（low+high)/2与low或hight的大小，再做下一步操作。
我们实现的方式采用非递归方式，代码如下：

/*非递归查找
数组元素为int，且递减 
返回值为int
数组的长度为len
查找值假设为key
*/

int BinSearch(int *Arr, int len, int key) {
	if (Arr == NULL || len <= 0) 
		return -1;
		
	int low = 0;
	int high = len - 1;
	int mid = 0;
	
	while (low <= hight) {
		mid = (low+high)/2;
		if (Arr[mid] > key)
			low = mid + 1;
		else if (Arr[mid] < key)
			high = mid - 1;
			else 
				return mid;
	}
	return -1;
}