美文网首页
数据结构与算法之美笔记——二分查找(上)

数据结构与算法之美笔记——二分查找(上)

作者: Cloneable | 来源:发表于2019-06-23 20:49 被阅读0次

摘要:

二分查找是一种高效的查找算法,时间复杂度为 O(\log{n}),但需要依赖有序数组。

原理

记得曾经看过一个节目的游戏环节,节目组会拿出一件商品,选手在规定时间内可多次对商品估价,选手每次估价主持人都会告诉选手,这个价格相对商品正确价格高了或者低了,选手根据此信息再次估价,直到规定时间结束或者估价正确,如果估价正确选手就可以免费获得此商品。

如果你是选手,你会如何以尽量少的次数猜中商品价格?二分查找就可以有效地解决此问题,二分查找会将「目标数据」(相当于商品价格)与一组数据中的「中间位数据」(相当于选手每次估价)比较大小,比较后会得到如下三个结论。

  1. 如果目标数据大于中间位数据,那目标数据位置处于第一位数据与中间位数据之间。
  2. 如果目标数据小于中间位数据,那目标数据位置处于最后一位数据与中间位数据之间。
  3. 如果目标数据等于中间位数据,那恭喜你已经猜中价格,可以拿走商品。

当中间位数据不等于目标数据时,可以确定目标数据在相应的数据子集中,在数据子集中继续采用二分查找,直至查到目标数据或者已经无子集可以查找。中间位数据的选择在数据总量是奇数时无可争议是最中间一位,当数据总量是偶数个时,我们将均分后较前的一位作为中间位数据。

假如商品价格为 58,需要在 0 至 100 的价格区间内猜出价格,具体步骤如下表:

数据范围 中间位数据 与目标数据比较
0 - 100 50 50 < 58
51 - 100 75 75 > 58
51 - 74 63 63 > 58
51 - 62 56 56 < 58
57 - 62 59 59 > 58
57 - 58 57 57 < 58
58 - 58 58 ✔️

代码实现

public int binarySearch(int[] a, int target) {
    if(a.length < 1) { return -1;}

    int high = a.length - 1;
    int low = 0;

    while(low <= high) {
        int mid = low + (high - low) / 2;

        if(target == a[mid]) {
            return mid;
        } else if(target > a[mid]) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;
}

实现中需要注意的几点如下:

  • 循环进入条件是 low \le high,因为当数组只有一位时也需要确定是否为目标数据
  • 计算中间点下标是使用 mid = low + (high - low) / 2,不直接使用 (low + high) / 2 的原因是如果 lowhigh 的数据比较大时可能会溢出,为了提高计算效率甚至可以使用位运算 low + ((high - low) >> 1)
  • low 和 high 的更新值为 low = mid + 1 high = mid - 1,如果更新取值为 mid 的话,当只有一个数据且此数据不等于目标数据的情况下 high 会一直等于 low,导致循环无法退出。

二分查找既然可以用循环实现,当然也可以转换为递归。

public int binarySearchRecursive(int[] a, int target, int low, int high) {
    if(low > high) {return -1;}

    int mid = low + ((high - low) >> 1);
    if(target == a[mid]) {
        return mid;
    } else if(target > a[mid]) {
        return binarySearchRecursive(a, target, mid + 1, high);
    } else {
        return binarySearchRecursive(a, target, low, mid - 1);
    }
}

效率分析

二分查找没有申请额外的存储空间,所以空间复杂度为 O(1),我们重点分析一下二分查找的时间复杂度。

二分查找每次都会将数据规模均分,数据规模会随着二分查找次数的增加依次为 n,\frac{n}{2},\frac{n}{2^2},\frac{n}{2^3},...,\frac{n}{2^k},k 表示查找到目标数据时进行二分的次数,查找到目标数据时数据规模为 1,所以 \frac{n}{2^k}=1,可以得到 k=\log{n},二分查找的时间复杂度就是 O(\log{n})

时间复杂度为 O(\log{n}) 的算法效率很高,甚至有时比 O(1) 的效率更高,比如数据规模是 2^{16}=65536 时二分查找只需要 16 次比较就可以找到目标数据,而 O(1) 只是表示常量级的时间复杂度,可确定的 1000, 10000 次时间复杂度也是 O(1),这种时候 O(\log{n}) 明显效率是高于 O(1) 的。

二分查找的劣势

二分查找虽然高效,但也有不可忽视的缺陷。

依赖顺序表结构

顺序表结构通俗一点讲就是数组。为什么会依赖数组,难道链表实现不可以吗?链表确实也能实现二分查找,使用链表实现与使用数组实现逻辑基本一致,只是在获取中间位数据时有区别,链表的特点使其在获取中间位数据时时间复杂度比数组高出很多,如果使用链表实现会导致二分查找的时间复杂度变高。

public int binarySearchLink(Link link, int target) {
    if(link == null || link.len < 1) {return -1;}
    LinkNode head = link.head;
    LinkNode tail = link.tail;
    int len = link.len;
    int start = 0;

    while(head != null && tail != null) {
        LinkNode mid = head, prev = null;
        int i = 1;
        for(; i < (len + 1) / 2; i++) {
            prev = mid;
            mid = mid.next;
        }

        if(target == mid.value) {
            return start + i;
        } else if(target > mid.value) {
            head = mid.next;
            len = i - len % 2;
            start = start + i;
        } else {
            tail = prev;
            tail.next = null;
            len = i -1;
        }
    }

    return -1;
}

public class Link {
    public LinkNode head;
    public LinkNode tail;
    public int len;
}

public class LinkNode {
    public int value;
    public LinkNode next;
}

观察代码,链表获取中间位数据需要遍历 \frac{n}{2} 的数据规模,时间复杂度也就是 O(n),如果用链表实现二分查找,二分查找的时间复杂度会变成 O(n\log{n}),这样的实现使二分查找损失了自己的优势。

需要有序数据

如果在一组无序数据中查找目标数据,将中间位数据与目标数据比较是无法确定目标数据坐落于哪个数据子集中,使用二分查找也就没有意义。所以无序数据想使用二分查找就需要将数据先排序,而排序算法时间复杂度是 O(n\log{n}),如果数据不会频繁变动(删除、插入),一次排序可以多次二分查找,排序的时间复杂度可以均摊到多次的二分查找上。如果无序数据频繁变动,会使时间复杂度提高,二分查找的效率也会降低,所以二分查找只适用于有序或者变动不频繁的数据。

过小/过大数据规模不适合

过小的数据规模遍历查找速度和二分查找速度相差不大,可以不使用二分查找。但数据比较操作耗时较多的情况下建议使用二分查找,毕竟二分查找可以减少数据比较次数。

由于二分查找依赖数组这种数据结构,数组的特点决定了当存储较大规模数据时容易出现内存溢出的问题。比如需要查找的数据为 1GB,内存剩余空间就算超过 1GB,但连续的存储空间没有 1GB 时相应大小的数组就无法申请成功,这也是导致二分查找不适用规模过大数据的原因。

总结

二分查找虽然高效,但在使用上具有依赖有序数组、不适合过大/过小数据规模的局限性,另外在代码实现上需要注意循环退出的条件、获取中点的方法及 low 和 high 的数据更新。


文章中如有问题欢迎留言指正
数据结构与算法之美笔记系列将会做为我对王争老师此专栏的学习笔记,如想了解更多王争老师专栏的详情请到极客时间自行搜索。

相关文章

  • 2019-10-27文章阅读

    二分查找(上):如何用最省内存的方式实现快速查找功能? 来源:王争的数据结构与算法之美时间复杂度为O(logn) ...

  • 二分查找

    学习极客时间的数据结构与算法之美的专栏,记录笔记。 1 二分查找应用场景的局限性 (1)二分查找依赖的是顺序表结构...

  • 数据结构与算法

    数据结构与算法之美 数据结构与算法之美1--如何学数据结构与算法之美2--复杂度分析(上)数据结构与算法之美3--...

  • 排序算法

    算法与数据结构基础 查找算法: 二分查找法: 简介:二分查找法又被称为折半查找法,用于预排序的查找问题 过程: 如...

  • 20181205_ARTS_W9

    Algorithm 数据结构与算法之美之变形二分查找大前提:都是有序数组,可能存在重复元素 查找第一个等于某个数值...

  • 数据结构与算法之美笔记——二分查找(上)

    摘要: 二分查找是一种高效的查找算法,时间复杂度为 ,但需要依赖有序数组。 原理 记得曾经看过一个节目的游戏环节,...

  • 如何学习数据结构与算法

    笔记源于极客时间《数据结构与算法之美》 什么是数据结构?什么是算法?从广义上讲,数据结构就是指一组数据的存储结构。...

  • 数据结构与算法--散列表

    数据结构与算法--散列表 之前学习了基于链表的顺序查找、基于有序数组的二分查找、二叉查找树、红黑树,这些算法在查找...

  • 数据结构与算法 树 引言 顺序查找 ​ 哨兵的方式 ​ 时间复杂度为O(N) 二分查找查找树的形式我...

  • 二分查找

    二分查找是一种查询效率非常高的查找算法。又称折半查找。 起初在数据结构中学习递归时实现二分查找,实际上不用递归也可...

网友评论

      本文标题:数据结构与算法之美笔记——二分查找(上)

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