#查找 之 二分查找 、二叉查找树
1. 二分查找
我们使用有序数组存储键，经典的二分查找能够根据数组的索引大大减少每次查找所需的比较次数。
在查找时，我们先将被查找的键和子数组的中间键比较。如果被查找的键小于中间键，我们就在左子数组中继续查找，如果大于我们就在右子数组中继续查找，否则中间键就是我们要找的键。
一般情况下二分查找都比顺序查找快的多，它也是众多实际应用程序的最佳选择。对于一个静态表（不允许插入）来说，将其在初始化时就排序是值得的。
当然，二分查找也不适合很多应用。现代应用需要同时能够支持高效的查找和插入两种操作的符号表实现。也就是说，我们需要在构造庞大的符号表的同时能够任意插入（也许还有删除）键值对，同时也要能够完成查找操作。
要支持高效的插入操作，我们似乎需要一种链式结构。当单链接的链表是无法使用二分查找的，因为二分查找的高效来自于能够快速通过索引取得任何子数组的中间元素。为了将二分查找的效率和链表的灵活性结合起来，我们需要更加复杂的数据结构。
能够同时拥有两者的就是二叉查找树。
public static int binarySearch(Integer[] srcArray, int des) {
//定义初始最小、最大索引
int low = 0;
int high = srcArray.length - 1;
//确保不会出现重复查找，越界
while (low <= high) {
//计算出中间索引值
int middle = (high + low)>>>1 ;//防止溢出
if (des == srcArray[middle]) {
return middle;
//判断下限
} else if (des < srcArray[middle]) {
high = middle - 1;
//判断上限
} else {
low = middle + 1;
}
}
//若没有，则返回-1
return -1;
}
比如：总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。
由于n/2^k取整后>=1，即令n/2^k=1，
可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn)
2. 二叉查找树
一颗二叉查找树（BST）是一颗二叉树，其中每个节点都含有一个可比较的键（以及相关联的值）且每个结点的键都大于其左子树中的任意结点的键而小于右子树的任意结点的键。
一颗二叉查找树代表了一组键（及其相应的值）的集合，而同一个集合可以用多颗不同的二叉查找树表示。
如果我们将一颗二叉查找树的所有键投影到一条直线上，保证一个结点的左子树中的键出现在它的右边，右子树中的键出现在它的右边，那么我们一定可以得到一条有序的键列。
查找代码几乎和二分查找的一样简单，这种简洁性是二叉查找树的重要特性之一。而二叉查找树的另一个更重要的特性就是插入的实现难度和查找差不多。