二分查找

一、定义

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。二分查找要求序列元素按关键字有序排列。

二、实现

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;
}

三、性能

对于一个含有N个键的有序数组，二分查找最多需要lgN+1次比较。

• 时间复杂度
  O(NlgN)