算法说明

又叫折半查找，要求待查找的序列有序。
每次取中间位置的值与待查关键字比较；
如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程；
如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。
直到查找到了为止，否则序列中没有待查的关键字。

示例代码

/**
 * 二分查找算法实现，返回查找数据在数组的序号。
 * @param array 数据
 * @param num 需要查询的数据
 * @return 数据序号
 */
public static int biSearch(int[] array, int num) {
    int start = 0;
    int end = array.length - 1;
    int mid;
    while(start <= end) {
        mid = (start + end) / 2;
        if(array[mid] == num) {
            return mid;
        } else if(array[mid] < num) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return -1;
}

调用示例：

public static void main(String[] args) {
    int[] array = { 1, 2, 4, 6, 8, 9, 10, 11, 12, 34, 55};
    int biSearch = biSearch(array, 9);
    System.out.println(biSearch);
}

算法复杂度

因为二分查找是一半一半的找，所以每次查找之后都会把查找范围减半；
比如说在一个 1 - 8 的有序数组里面查找 8 也就是查找最坏情况。
在数组当中完成二分查找需要 log2n - 1 次；
也就是时间复杂度是 log2n （就是 log 以 2 为底 n 的对数）