一、定義

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。二分查找要求序列元素按關(guān)鍵字有序排列。

二、實(shí)現(xiàn)

public int binarySearch(int[] arr, int key) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (key == arr[mid]) {
            return mid;
        } else if (key < arr[mid]) {
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    return -1;
}

三、性能

對(duì)于一個(gè)含有N個(gè)鍵的有序數(shù)組，二分查找最多需要lgN+1次比較。

• 時(shí)間復(fù)雜度
  O(NlgN)