伪代码

l：left，即当前区间最左边的元素下标        A：数组名

r：right，即当前区间最右边的元素下标        n：数组长度

m：middle，即(左区间区间元素下标+右区间元素下标)/2。

C++实现

int binarySearch(int* nums, int x, int n)
{int runTimes = 0;int left = 0, right = n - 1;while (left <= right){int middle = (left + right) / 2;runTimes++;if (x == nums[middle]){cout << "RunTimes:" << runTimes << endl;return middle;}if (x > nums[middle]){left = middle + 1;}else{right = middle - 1;}}cout << "RunTimes:" << runTimes << endl;return -1;
}

原理

给定一个已经排好序的数组（n个元素，数组范围是[0,n-1])，现要使用二分查找找出一个特定元素x。

先将数组分为左区间和右区间，如果此处数组中间值nums[middle]恰好等于要找的x，算法终止。

如果不等，就将x与数组中间值nums[middle]比较大小，由于数组已经是有序的，我们可以知道我们要找的特定元素x是在左区间还是右区间。此时只需再取左/右区间并重复：区间二分--比较是否相等，相等则返回此时middle，即特定元素的下标--不相等则根据大小再取左/右区间。

时间复杂度相关

Q：对于该算法，假设有个元素，最多经过几次比较，算法停止？

最多k次。从“最多”我们可以知道要找的元素x应该在数组开头nums[0]或数组尾部nums[n-1]这两个位置。

经过第一次二分后，那么此时左/右还有即个元素。重复该过程直到剩下个元素，从1到k一共要经过k次比较。

Q：时间复杂度是多少

，其实不太严谨。至于底数要看分治的复杂度，二分法底数为2，三分法底数为3....，当然不写底数也行，但是得知道它底数怎么看。

Q：时间复杂度如何计算

假设我们要查找的元素为x。数组中总共有个元素，x在每个位置的概率相等。

先看看最坏情况时间复杂度。从Q1我们已知，要经过k次比较。我们用n来表示k：。当k足够大时，，那么此时。我们便得到了最坏情况时间复杂度。（省略底数）

最优情况复杂度没啥，第一次二分就找到那复杂度就为1。

平均时间复杂度。计算过程太长这里就不列出来了。

我们一般把最坏时间复杂度当作算法的时间复杂度，所以二分查找法的时间复杂度就是。

测试用样例（C++）

#include 
using namespace std;int binarySearch(int* nums, int x, int n)
{int runTimes = 0;int left = 0, right = n - 1;while (left <= right){int middle = (left + right) / 2;runTimes++;if (x == nums[middle]){cout << "RunTimes:" << runTimes << endl;return middle;}if (x > nums[middle]){left = middle + 1;}else{right = middle - 1;}}cout << "RunTimes:" << runTimes << endl;return -1;
}
int main()
{int n;cin >> n;int* nums = new int[n];//Example:7 1 12 13 14 21 31 41 for (int i = 0;i < n;i++){cin >> nums[i];}int key;cin >> key;int index=binarySearch(nums, key, n);if (index != -1)cout << "index:" << index << " " << nums[index] << endl;elsecout << "Not Found" << endl;
}