再送你6本奇书！

—————  第二天  —————

如何进行二分查找呢？

首先根据数组下标，定位到数组的中间元素：

由于要查找的元素20，大于中间元素12，再次定位到数组右半部分的中间元素：

这一次定位到的元素正好是20，查找成功。

如果数组的长度是n，二分查找的时间复杂度是O（logn），比起从左到右逐个遍历元素进行查找的方式，大大提升了查找性能。

如上图所示，想要定位到链表的中间结点9，是无法直接定位的，需要从头结点开始，顺着next指针，逐个访问下一个结点。

因此，链表这种数据结构并不适用于二分查找。

————————————

常见的图书目录，就像下面这样：

第5章对应的页码是170，因此我们直接翻到书的第170页，就是第5章的内容。

如图所示，在原始链表的基础上，我们增加了一个索引链表。原始链表的每两个结点，有一个结点也在索引链表当中。

这样做有什么好处呢？当我们想要定位到结点20，我们不需要在原始链表中一个一个结点访问，而是首先访问索引链表：

在索引链表找到结点20之后，我们顺着索引链表的结点向下，找到原始链表的结点20：

这个过程，就像是先查阅了图书的目录，再翻到章节所对应的页码。

由于索引链表的结点个数是原始链表的一半，查找结点所需的访问次数也相应减少了一半。

你知道这个问题的答案吗？

上面的漫画出自算法大佬小灰的作品《漫画算法2》中，问题的答案可以在这本书中找到，像这样漫画讲解算法的文章，小灰哥写了许多，他的第一部作品《漫画算法》就曾创下过编程类书籍的销量神话。

不久前，小灰的《漫画算法2》终于正式上市了：

好消息是，我跟出版社的小姐姐说了不少好话，她答应送我 6 本书送给读者。

欢迎大家在评论区留言，说出想要这本书的理由，我将放出有诚意的留言，48小时内点赞数最高的前六名获得送书哦。

哦对了，为了防止羊毛党，本次送书只限发文前已关注的朋友。新看到的朋友不要走开，顺手点个关注，下周再送另外的书，还有机会哈。

点个[在看]，是对我最大的支持！