二分查找有着查找速度快，平均性能好等优点，但必须要求待查表为有序表，且插入删除困难

private static int binarySearch0(int[] a, int fromIndex, int toIndex,int key) {        int low = fromIndex;        int high = toIndex - 1;                /* 如果改为 low < high，就有可能出现本来数组中有待查元素，却查不到的情况          比如查10，前两次查找和查12一样，最后low和high指向了元素10，          但是此时while(low
     
      >> 1;//使用位操作,效率高            int midVal = a[mid];            if (midVal < key)                low = mid + 1;            else if (midVal > key)                high = mid - 1;            else                return mid; // 找到目标        }        return -(low + 1);  // 没找到目标.    }
     

复杂度分析

你要查找的数据规模如果是n,那二分一次后规模就变为n/2^{1,二分两次后规模为n/2}2,...,二分m次后规模为n/2^m,若二分m次后跳出循环，则m就是循环的次数（不管查找是否成功）

最坏情况（即查不到）

假设二分m次后剩下一个元素，那么此时规模为1,同时二分m次后规模变为n/2^{m，则：n/2}m = 1, 解出 m = lg(n)，此时再循环一次，查找不到，跳出循环，所以说最多有 m+1 次循环（二分m次未跳出循环，还要二分一次），也就是查找一个元素最多需要m+1次，即lg(n)+1次比较，故二分的最坏时间复杂度为O(n) = lg(n)

折半后，要对一半元素进行遍历，复杂度是O(n),所以算法的时间复杂度为O(n * lg(n))