概述

二分查找在对有序列表中进行查找时比较高效的一种查找算法。它的基本思想是在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等则算查找成功，若给定值小于中间记录的关键字，则在中间记录的左半区继续查找，若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止（大话数据结构）

时间复杂度

二分查找等于在有原数据构成的二叉树进行查找，所以时间复杂度为O(logn)

例子

public class BinarySearch {
    private static int binarySearchIndex(int[] array, int key) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int length = array.length;
        int low = 1;
        int high = length -1;
        int mid;
        while (low <= high) {
            mid = (high - low) / 2;
            if (array[mid] < key) {
                low = mid + 1;
            } else if (array[mid] > key){
                high = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        int[] array = new int[] {0,1,16,24,35,47,59,62,73,88,99};
        System.out.println( binarySearchIndex(array, 35));
    }
}

上面用Java实现了一个二分查找，当数据量不大时执行效率跟遍历查找不太容易看出来，但是数据量很大的情况下就有感觉。