树结构是如何进行二分查找的？
上一讲我们讲了，因为链表并不具备 随机访问 的特点，所以二分查找无法生效。当链表想要访问中间的元素时，我们必须从链表头开始，沿着指针一步一步遍历，需要遍历一半的节点才能到达中间节点，时间代价是 O(n/2)。而有序数组由于可以 「随机访问」，因此只需要 O(1) 的时间代价就可以访问到中间节点了。
那如果我们能在链表中以 O(1) 的时间代价快速访问到中间节点，是不是就可以和有序数组一样使用二分查找了？你先想想看该怎么做，然后我们一起来试着改造一下。
直接记录和访问中间节点
既然我们希望能以 O(1) 的时间代价访问中间节点，那将这个节点直接记录下来是不是就可以了？因此，如果我们把中间节点 M 拎出来单独记录，那我们的第一步操作就是直接访问这个中间节点，然后判断这个节点和要查找的元素是否相等。如果相等，则返回查询结果。如果节点元素大于要查找的元素，那我们就到左边的部分继续查找；反之，则在右边部分继续查找。
对于左边或者右边的部分，我们可以将它们视为两个独立的子链表，依然沿用这个逻辑。如果想用 O(1) 的时间代价就能访问这两个子链表的中间节点，我们就应该把左边的中间节点 L 和右边的中间节点 R，单独拎出来记录。
并且，由于我们是在访问完了 M 节点以后，才决定接下来该去访问左边的 L 还是右边的 R。因此，我们需要将 L 和 M，R 和 M 连接起来。我们可以让 M 带有两个指针，一个左指针指向 L，一个右指针指向 R。这样，在访问 M 以后，一旦发现 M 不是我们要查找的节点，那么，我们接下来就可以通过指针快速访问到 L 或者 R 了。
将 M 节点改为带两个指针，指向 L 节点和 R 节点
对于其余的节点，我们也可以进行同样的处理。下面这个结构，你是不是很熟悉？没错，这就是我们常见的二叉树。你可以再观察一下，这个二叉树和普通的二叉树有什么不一样？
没错，这个二叉树是 有序 的。它的左子树的所有节点的值都小于根节点，同时右子树所有节点的值都大于等于根节点。这样的有序结构，使得它能使用二分查找算法，快速地过滤掉一半的数据。具备了这样特点的二叉树，就是 二叉检索树（Binary Search Tree），或者叫 二叉排序树（Binary Sorted Tree）。
讲到这里，不知道你有没有发现，尽管有序数组和二叉检索树，在数据结构形态上看起来差异很大，但是在提高检索效率上，它们的核心原理都是一致的。那么，它们是如何提高检索效率的呢？核心原理又一致在哪里呢？接下来，我们就从两个主要方面来看。
● 将数据有序化，并且根据数据存储的特点进行不同的组织。对于连续存储空间的数组而言，由于它具有「随机访问」的特性，因此直接存储即可；对于非连续存储空间的有序链表而言，由于它不具备「随机访问」的特性，因此，需要将它改造为可以快速访问到中间节点的树状结构。
● 在进行检索的时候，它们都是通过二分查找的思想从中间节点开始查起。如果不命中，会快速缩小一半的查询空间。这样不停迭代的查询方式，让检索的时间代价能达到 O(log n) 这个级别。
