查找-二分查找Binary Search

查找-二分查找Binary Search

相信大家都玩过小时候的猜数字游戏:A想一个100以内的数,大家来猜这个数,谁的次数最少谁就获胜。这大概是我们最早接触二分查找了,二分查找是查找算法中效率比较高而且也比较简单的算法,但是使用上会有一些限制,比如需要查找集合是顺序存储的有序表。


一、简述

二分查找又叫折半查找,需要在顺序存储有序表(随机访问)中进行查找。

它的整体思想比较简单易懂,先与顺序表中间元素进行对比,

  • 等于中间元素则查找成功;
  • 大于中间则在右边子表以同样的方式查询;
  • 小于中间则在左边子表以同样的方式查询;

(注意上面的大于小于等于只是抽象的概念,并非只是数字比较,具体的规则有我们自己定义。)

二、算法实现

1、迭代(非递归)

int binarySearch(int key, int[] array, int low, int high) {
    if (array.length == 0 || low < high ||
            key > array[high] || key < array[low]) {
        return -1;
    }
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (key == array[mid]) {
            return mid;
        } else if (key < array[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

2、递归

一般来说二分用迭代循环就好了,不推荐用递归,递归的空间消耗更大。这里可以加深下递归思想的理解。

int binarySearch(int key, int[] array, int low, int high) {
    if (array.length == 0 || low > high ||
            key > array[high] || key < array[low]) {
        return -1;
    }
    if (low <= high) {
        int mid = (low + high) / 2;
        if (key == array[mid]) {
            return mid;
        } else if (key < array[mid]) {
            return binarySearch(key, array, low, mid - 1);
        } else {
            return binarySearch(key, array, mid + 1, high);
        }
    }
    return -1;
}

三、分析

每次查找的范围减少一半,很明显二分查找的时间复杂度是 O(h)=O(lgn) 

二分查找很快,但是限制条件也比较多,光是有序条件就比较麻烦,如果维护有序的代价不小的话,就需要权衡了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注