二分查找法的一些思考

分享 AIZero ⋅ 于 2020-06-28 18:09:32 ⋅ 最后回复由 青牛 2020-06-28 18:29:03 ⋅ 143 阅读

零基础跟了老师一个月,思维导图不会弄,期间学了一些算法可以做一些分享,请大家指正
查找长度:关键码的比较次数,评估查找算法的性能

1. 二分查找法的一般写法

class BinarySearch1 { // high设置为数组下标末端的后一位,即为arr.length,最后会分析原因
    public int search(int[] arr, int key, int low, int high) {
        while (low <= high) {
            int mid = (low + high) / 2;
            int midVal = arr[mid];
// 这里的判断条件如果先是key == midVal,判断的次数会更多,算法性能会下降
            if (key < midVal) { 
                high = mid - 1;
            }else if(midVal < key){
                low = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}

查找长度分析:每一次判断,如果目标值在midVal左侧,只需要进行一次判断就可以转向,但是目标值在midVal右侧,需要进行两次判断才可以转向。

如果将第一个条件判断语句改为key == midVal ,则无论目标值在左侧和右侧都需要两次判断,这样反而会降低效率。

查找长度的精确计算

我们不妨设定high与low的差值为2^k,那么数组长度为2^k-1。其中设C(k-1)总体查找长度,当进行一次二分查找时,当降维为C(k-1)时,左侧每个元素少比较一次,右侧每个元素少比较两次,如果命中还需两次比较。综上得出如下表达式:
$$
\begin{aligned}

&C(k) = [C(k-1) + (2^{k-1}-1)] + 2 + [C(k-1) + 2(2^{k-1} -1)]= 2C(k-1) + 32^{k-1} -1 \
&(C(k)-1.5k2^{k} -1) = 2(C(k-1)-1.5(k-1)2^{k-1} -1)

\end{aligned}
$$

用数列不断向下迭代,由C(1)= 2可以得出一般通式,然后除以元素个数得出每个元素被取到的平均长度
$$
\begin{align}
&C(k) = 3k
2^{k-1} - 2^k+1 = (3k/2 -1)(2^k-1) +3k/2 \
&C_{average} \approx 3k/2
\end{align*}
$$

将n带入得到二分查找法的时间复杂度为
$$
\sigma(1.5k) = \sigma(1.5log_2n)
$$

优化的思考

  • 目标值左侧转向需要一次判断,目标值右侧转向需要二次判断,既然左侧判断成本低,分割点往右侧移动会整体降低判断成本。

  • 分割点的位置应该设在哪里?

2. 黄金分割查找算法(斐波那契查找算法)

分割点位置分析

对优化思路进行抽象:计算稍微有点麻烦,还可以接受
$$
\begin{aligned}
&将数组长度设为n,\lambda为切分点,区间在[0,1),设置平均查找长度为a(\lambda)log_2n,何时a(\lambda)最小?\
&a(\lambda)
log_2n = \lambda[1+a(\lambda)log_2(\lambdan)]+(1-\lambda)[2+a(\lambda)log_2((1-\lambda)n)]\
&化简得到\frac{ln2}{a(\lambda)} = \frac{\lambda
ln\lambda+(1-\lambda)ln(1-\lambda)}{\lambda-2}\
&微分求到a(\lambda)获得最小值的条件为ln(1-\lambda)-2ln\lambda =0\
&当\lambda为\frac{\sqrt{5}+1}{2}(即黄金分割点处),a(\lambda)取得最小值约为1.44\
&时间复杂度的极限为\sigma(1.44log_2n)
\end{aligned}
$$
总体来看,黄金分割查找算法对普通的二分查找算法起到了优化效果,是在常系数上起到了作用

// 斐波那契查找算法
public class FibSearch {
    // 构造斐波那契数列,可以用动态规划法对其优化
    public static int[] fib() {
        int[] f = new int[20];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < 20; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }
    // 实现斐波那契排序算法
    public static int fibSearch(int[] arr, int key, int low, int high) {
        int k = 0;
        int mid = 0;
        int f[] = fib();

        while (high > f[k]) {
            k++;
        }
        int[] temp = Arrays.copyOf(arr, f[k]);
        for (int i = high; i < temp.length; i++) {
            temp[i] = arr[high - 1];
        }

        while (low <= high) {
            mid = low + f[k - 1] - 1;
            if (key < temp[mid]) {    // 判断要先判断左侧,来让左侧转向发挥最大效用
                high = mid;        
                k--;
            } else if (key > temp[mid]) {
                low = mid + 1;
                k -= 2;
            } else {
                if (mid < high) {
                    return mid;
                } else {
                    return high - 1;
                }
            }
        }
        return -1;
    }
}

优化的思考

上面两种查找算法比较类似快速排序分区的想法,都是如果正好找到值则立马结束,返回下标位置,但也正是因为如此造成了查找长度的不平衡。

3. 二分查找法的优化

优化的思路

为了平衡查找长度,我们可以借鉴归并排序的想法,直接将数组一分为二,即使能命中目标值,也不急于返回,从整体上提升性能

class BinarySearch2{
     public int search(int[] arr, int key, int low, int high) {
        while (low + 1 < high) {
            int mid = (low + high) / 2;
            int midVal = arr[mid];

            if (key < midVal) {
                high = mid;
            }else if(midVal < key){
                low = mid;
            }
        }
        return (key == arr[low])? key : -1 ;
    }
}

查找长度精确计算:与第一种方法类似,我这里直接写结果
$$
\begin{align}
&C(k) = k
2^{k} - 2^k+1 = (k -1)(2^k-1) +k \
&C_{average} \approx k
\end{align*}
$$
将n带入得到二分查找法的时间复杂度为
$$
\sigma(k) = \sigma(log_2n)
$$
综合来看:两种二分查找法比较来看,后者在最好的情况下不如前者,最坏的情况下优于前者,但时间复杂度整体上得到优化

优化的思考

  • 第二种二分查找法似乎已经到了优化的极限,但是二分查找的目标不仅仅在于找到,还有一个关键是没找到时该返回何种数值
  • 当查找的数字不在数组中或者查找的目标个数存在多个,我们希望返回的值能为key的插入提供指导,比如key有多个,返回最后一个;key比整体小,则返回头部的位置; key比整体大,则返回尾部的位置
  • while中的判断方法low + 1 < high这种判断方法对上述的情况有助力吗?

4. 二分查找的最终优化

优化的思路

  • 数轴的表示方式,在数轴上表示数细想起来还是有挺多细节的,在整数数组中,对于一个数字2,[2,3)表示一个2,在数轴上表示为一段区间,[2,2)表示一条线,在数轴上表示2区间的前界,同时也是1区间的后界。同理[3,3)表示2区间的后界。
  • 一般都会采取前界或者一个区间来表示一个数的具体位置,但在当下这个场景并非最好的选择。特别是碰到多个相同key元素时为后续插入位置提供位点时,只有通过后界来跳出循环才能实现。
  • 通过数字后界来返回数组能完美解决key在数组左右侧,多次出现的问题,为后续的插入位置提供方向,只需在返回值+1即可。
  • high之所以选择arr.length而不是arr.length-1,是为了服务key大于数组所有元素,保证插入位置的准确。
class BinarySearch3 {
    public int search(int[] arr, int key, int low, int high) {
        while (low < high) {
            int mid = (low + high) / 2;
            int midVal = arr[mid];

            if (key < midVal) {
                high = mid;
            }else{
                low = mid + 1;  // 代码的核心
            }
        }
        return --low;  
    }
}

总体分析:目前是二分查找最终优化版本,在算法性能和返回值上都很不错。

5. Java的二分查找的源码分析

private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

源码的分析

  1. 从时间复杂度来看,并没有做到最优化
  2. 从意外返回值的类型来分析
    • 如果key在数组左侧,返回值 -1
    • 如果key在数组右侧,返回值为为负数
    • 如果存在多个key值,无法返回key最末端元素
  3. 此种返回值的好处为找到为整数,没找到为负数,这是优势的地方。
版权声明:原创作品,允许转载,转载时务必以超链接的形式表明出处和作者信息。否则将追究法律责任。来自海牛部落-AIZero,http://hainiubl.com/topics/75165
本帖已被设为精华帖!
本帖由 青牛 于 1周前 加精
回复数量: 5
  • 青牛 国内首批大数据从业者,就职于金山,担任大数据团队核心研发工程师
    2020-06-28 18:11:46

    优秀,打赏5元

  • AIZero
    2020-06-28 18:16:14

    @青牛 数学表达式没有输出来有点可惜,数学忘了的我算了好久

  • 青牛 国内首批大数据从业者,就职于金山,担任大数据团队核心研发工程师
    2020-06-28 18:19:06

    @AIZero 你是说发不了数学公式吗?数学表达式你可以贴图啊

  • AIZero
    2020-06-28 18:26:52

    @青牛 在文档里写的能显示,我下次会贴图,这次的计算过程可以忽略的

  • 青牛 国内首批大数据从业者,就职于金山,担任大数据团队核心研发工程师
    2020-06-28 18:29:03

    @AIZero 高端选手啊,都整上公式推导了。咱们这贴图很简单的截屏然后ctrl+V。

暂无评论~~
  • 请注意单词拼写,以及中英文排版,参考此页
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`, 更多语法请见这里 Markdown 语法
  • 支持表情,可用Emoji的自动补全, 在输入的时候只需要 ":" 就可以自动提示了 :metal: :point_right: 表情列表 :star: :sparkles:
  • 上传图片, 支持拖拽和剪切板黏贴上传, 格式限制 - jpg, png, gif,教程
  • 发布框支持本地存储功能,会在内容变更时保存,「提交」按钮点击时清空
Ctrl+Enter