数据结构与算法分析之二分查找

什么是二分查找？

二分查找（binary search）又叫折半查找，它是一种在有序数组中查找某一特定元素的搜索算法。

二分查找必要条件？

• 必须为顺序存储结构；

• 必须按关键字大小有序排列。

二分查找原理

使用二分查找算法找出arrays数组中8的位置

int[] arrays = new int[] {2,8,12,18,20,25,30,37,41,49,61};

• 将有序数组分为三个部分，分别为中间值前（中间值数之前的一组数据），中间值和中间值后（中间值之后的一组数据）；

• 将要查找的数与中间值的数相比较，等于则退出查找，小于则在中间值前进行比较，大于在在中间值后进行比较，依次递归，直至查找到对应的值为止；

• 当要查找数据结构为偶数时，中间值mid应向下取整处理；

• 上述arrays数组中间值为{25}，中间值前为{2,8,12,18,20}，中间值后为{30,37,41,49,61}。

二分查找计算原理图，如下：

二分查找常用两种方式：

• 递归查询

递归查询

• 非递归查询

非递归查询

• main方法

时间复杂度和空间复杂度

时间复杂度：

• 最坏的情况下两种方式时间复杂度一样：O(log2 N);

• 最好情况下为O(1);

空间复杂度：

算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数

• 非递归方式：由于辅助空间是常数级别的所以：空间复杂度是O(1);

• 递归方式：递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的：空间复杂度：O(log2N )。

二分查找中值(mid)计算 二分查找中值计算有两种方式：

• int mid = (low + high) / 2;

• int mid = low + (high - low) / 2;

上述两种算法看似第一种要简洁，第二种提取之后，跟第一种没有什么区别。但是实际上上述两种计算是有区别的，第一种的做法是在极端情况下计算的，(low + high)存在着溢出的风险，进而有可能得到错误的mid结果，导致程序错误；而第二种算法能够保证计算出来的mid值一定大于low、小于high，不存在溢出的问题。 针对第一种算法为了防止溢出问题，可以使用：int mid = (high + low) >>> 1; 解决此问题。

二分查找的优缺点：

• 优点：比较次数少，查找速度快，平均性能好。

• 缺点：必须有序，必须是数组。

引申

解决二分查找缺陷问题更好的方法是使用二叉查找树，最好自然是自平衡二叉查找树，既能高效的（O(n log n)）构建有序元素集合，又能如同二分查找法一样快速（O(log n)）的搜寻目标数。