对于二分查找算法，相信大家肯定不会陌生。算法从一个排好序的数组中找指定的元素，如果找到了返回该元素在数组中的索引，否则返回-1。下面给出了解法。
//a为排好序的数组，n为数组的大小，x为指定元素 int binarySearch(int a[], int n, int x) { int left = 0, right = n-1, middle = 0; int tmp = 0; while(left <= right) { middle = (left + right)/2; tmp = a[middle]; if(x < tmp) right = middle - 1; else if(x > tmp) left = middle + 1; else return middle; } return -1; }
乍看没有错误，但是不幸的是，该程序存在一个bug。当数组极大时，(left+right)可能为负数，则数组下标溢出，程序崩溃。
解决的方案：将middle=(left+right)/2改为middle=left+(right-left)/2即可。即利用减法代替加法，从而消除上溢。
参考自《代码之美》
