三、算法实践
1. 算法实现
输入数据（input）：A = {10，11，12，14，20，32，34，35，41，43}，key = 11
Java源代码
需要注意源代码与伪代码的区别，请查看文章开头补充的概念部分，这里不做过多说明。
public class BinarySearch { public static void main(String[] args) { // input data int[] a = {10,11,12,14,20,32,34,35,41,43}; int key = 11; // 调用算法，并输出结果 int result = search(a, key); System.out.println(result); } private static int search(int[] a,int key){ // 初始化变量 int left = 0; int right = a.length - 1; // 循环终止条件为：左右端点发生交错 while (left <= right){ // 取中间元素，以下写法防止数据量较大时发生溢出 int mid = (right - left) / 2 + left; if (a[mid] == key){ // 情况1：与key相等 return mid + 1; }else if(a[mid] > key){ // 情况2：比key大 right = mid - 1; }else { // 情况3：比key小 left = mid + 1; } } // 循环结束还未触发内部的return则代表未找到，此时返回-1 return -1; } }
执行效果
输出数据（output）：2
2. 时间复杂度
最坏的情况
最坏的情况就是直到最后一次才找到key，或者查找失败的情况。那么也就是说我们只要能计算出最多会找多少次，就能知道最快的情况。
可以知道，寻找的最大次数肯定是与n相关的，由于每次区间都缩小一半。所以这个问题就好比一根绳子，最多被折多少次，直到最后剩下一个元素（不能再折）为止。所以就是一个以2为底，相对于n的对数O( log 2 n \log _{2} n log2n) ，这也就是循环最多会执行的次数（循环内部的代码都是常量级别）。
最好的情况
对于二分查找来说最好的情况就是第一次就找到了key，也就是一脚定乾坤了，此时的时间复杂度为常数级：O(1) 。
平均情况
综合两种情况，二分查找的时间复杂度为O( log 2 n \log _{2} n log2n) 。
3. 空间复杂度
由于算法不会改变原有的元素集合，只需要几个额外的变量记录关键信息，所以空间复杂度为常数级：O(1) 。
