一.什么是二分搜索

二分搜索（Binary Search），是一种在有序数组中查找特定元素的高效算法。

二分搜索算法,实际上就是对一颗BST树从root根节点开始搜索的过程,每一次搜索只会沿着一条路径搜索下去

核心思想:是每次定义索引left与right，每次找一个mid，比较mid索引的值与应找值val，之后缩小查找范围，循环操作，直到找到val或者循环结束。

二.非递归代码实现

非递归实现二分搜索借助循环，直到left小于等于right循环结束。

int BinarySearch(int arr[], int size, int val)//二分搜索（非递归）
{
	int left = 0;
	int right = size - 1;
	int	middle = (left + right)/2;
	while (left <= right)
	{
		if (val == arr[middle])
		{
			return middle;
		}
		else if (val < arr[middle])
		{
			right = middle - 1;
			middle = (left + right) / 2;
		}
		else
		{
			left = middle + 1;
			middle = (left + right) / 2;
		}
	}
	return -1;

}

三.递归代码实现

递归代码实现借助递归代替循环，核心思路相同。

二分搜索（递归）
int BinarySearch(int arr[], int val,int i,int j)
{
	int mid = (i + j) / 2;
	if (i > j)
	{
		return -1;
	}
	else if(val<arr[mid])
	{
		return BinarySearch(arr, val, i, mid - 1);
	}
	else if (val > arr[mid])
	{
		return BinarySearch(arr, val, mid+1, j);

	}
	else if (val == arr[mid])
	{
		return mid;
	}

}

四.二分搜索的时间复杂度

由于二分搜索实际上是对BST树，从root根节点开始搜索的过程，所以二分搜索的平均时间复杂度为logn。空间复杂度为O(n)。