二分查找

作者: null12 | 来源:发表于2018-03-21 20:17 被阅读0次

一、定义

二分查找也称折半查找(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)

相关文章

网友评论

    本文标题:二分查找

    本文链接:https://www.haomeiwen.com/subject/epsnqftx.html