1.二分查找法思想

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是：（这里假设数组元素呈升序排列）将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止；如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x；如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。[引自百度百科]

2.算法使用前提

1.必须采用顺序存储结构。
2.必须按关键字大小有序排列。

注：顺序存储结构-------逻辑上相邻的结点存储在物理位置上相邻的存储单元中，比如数组等结构

3.递归实现（C++）

#include <iostream>
using namespace std;
//二分查找发C++实现
int binarySearch(int a[], int x, int left, int right);//函数声明
int main()
{
	int a[] = {1,2,3,4,5,6,7,8,9};
	//int mark = binarySearch(a, 6, 0, sizeof(a)/sizeof(a[0]) - 1);//sizeof(a)/sizeof(a[0])为数组a的长度
	int mark = binarySearch(a, 11, 0, sizeof(a) / sizeof(a[0]) - 1);//sizeof(a)/sizeof(a[0])为数组a的长度
	if (mark == -1)
		cout << "未查找到" << endl;
	else
		cout << "查找到，下标为：" << mark << endl;
	
}
//数组a从小到大排列
int binarySearch(int a[], int x, int left, int right)
{
	//还可以做优化
	int mid = (left + right) / 2;
	if (a[mid] == x)
		return mid;
	else if(left == right)
		return -1;//表示没有找到
	else if (a[mid] < x)
		binarySearch(a, x, mid + 1, right);
	else if (a[mid > x])
		binarySearch(a, x, left, mid-1);
}

这里实现的功能是：查找整型数组a（升序）中是否存在某个整数，如果存在返回其在数组中的下标，如果不存在返回-1
其中算法可以进一步优化，比如，先判断x的范围是否在数组a[0]到a[len(a)-1]中，如果不在直接返回-1

4.非递归实现（C++）

递归算法改成非递归，是广大计算机从业者必须掌握的一个技能。
原因在于：
1.在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出。
2. 递归算法虽简洁，但运行效率较低，有很大优化的空间

递归算法->非递归算法

将递归算法转换为非递归算法有两种方法，一种是直接转化法，不需要回溯，使用一些变量保存中间结果；另一种是间接转化法，需要回溯，使用栈保存中间结果。

（1）直接转化法

将递归结构用循环结构来替代

#include <iostream>
using namespace std;
//二分查找发C++实现
int binarySearch(int a[], int x, int left, int right);//函数声明
int main()
{
	int a[] = {1,2,3,4,5,6,7,8,9};
	int mark = binarySearch(a, 6, 0, sizeof(a)/sizeof(a[0]) - 1);//sizeof(a)/sizeof(a[0])为数组a的长度
	//int mark = binarySearch(a, 11, 0, sizeof(a) / sizeof(a[0]) - 1);//sizeof(a)/sizeof(a[0])为数组a的长度
	if (mark == -1)
		cout << "未查找到" << endl;
	else
		cout << "查找到，下标为：" << mark << endl;
	
}
//数组a从小到大排列
int binarySearch(int a[], int x, int left, int right)
{
	int mid = -1;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (a[mid] == x)
			return mid;
		else if (a[mid] < x)
			left = mid + 1;
		else if (a[mid > x])
			right = mid - 1;
	}
	//while跳出循环时
	return -1;//表示没有找到
}