【算法分析与设计】二分查找算法面面观

2019年10月7日 2点热度 0条评论 来源: 星拱北辰

二分查找概述

二分查找的代码很久之前已经用Java、C、Python等语言实现过了,对于初学者也是很容易做的。
学习二分查找的关键在于掌握二分查找的思想,个人认为编程语言不应该是限制我们写基本算法的障碍

但还是更一下Java版的二分查找代码吧……(Update on 2020/2/9,见文末)
更是有广义版本的新代码(Update on 2020/2/25,见文末)

(二分查找).compareTo(分治法)

需要说明,二分查找和分治法不一样,不要弄混淆……

二分查找 每次都舍弃一半,从留下的一半中寻找目标
而分治法把一个大问题分成两个或多个小问题,递归地求这些小问题的解,最后再把它们合并起来,并且要仔细考虑合并时产生的新的情况。

其实二分查找严格来讲可以说是“减治法”,要是宽泛的讲也可说是“分治法”。(Update on 2020/2/9)

二分查找有对数阶的效率

由于二分查找每次都丢弃一半的区间,所以能逐步的简化问题求解,特别是在数据量庞大的时候会有很好的效率。

O(logN),对数级别啊,很棒啊……最坏情况是log2n次比较!!!

试想:比如给出一个220=1048576‬数据量的数组,我们假设能分配出来。(Update on 2020/2/11)
二分查找大致最坏需要log2220=20次查找,而线性复杂度的顺序查找就可能要查220=1048576‬次,差别巨大。

二分查找要求序列是有序的

二分查找需要先排序,因为只有有序的数组or顺序表等才能二分查找来比较。
试想,不排序,怎能在low~high之间不断精确的缩小范围,怕不是要彻底混乱?

一定要有序,我们如果想使用二分查找,就需要维护有序数组

不得不说,二分查找比起顺序查找优化了很多,但要求是有序啊,君不知这排序效率可是O(NlogN)啊,所以说为了二分查找而二分查找是没必要的。(Update on 2020/2/11)

不标准的mid = (high+low)/2

二分查找要防止溢出,这个说法有道理。
在学校上课的时候,老师告诉我们:mid = (high+low)/2 是标准解,也曾被我奉为圭臬。
然而,试想:但是如果high+low溢出而mid、high、low均不溢出呢?是不是要做一下处理呢?有一种较好的解答是这样的:
mid = left + (right - left)/2
这样的话就解决了那样一个问题,建议初学者规范一下自己写的二分查找哇!

当然,比如说Java的源代码就用的是mid = high + low >>> 1,相当于mid = (high+low)/2,为什么合理呢?

事实上,Java数组的长度上限是Integer.MAX_VALUE,然而能达到那个程度的数组一般在内存里分配不出来,会分配失败的。故而想通过简简单单的加法就爆掉int,恐怕没有实际发生的可能呢。

Python编写简单二分查找

既然写到这里了,就用Python简单地编写一下吧(没测试):

def binarySearch(l, value):
    low, high = 0, len(l)-1
    while low < high:
        # 这里建议规范一下
        mid = low + (high - low)//2
        if l[mid] < value:
            # 向上缩小区间
            low = mid+1
        elif value < l[mid]:
            # 向下缩小区间
            high = mid-1
        else:
            # 找到了
            return mid
    # 没找到
    return -1

┭┮﹏┭┮,Python简单嗷~~~

为什么不是三分查找

比较二分查找和三分查找:
二分查找将先比较n/2,然后区间分成[0, n/2-1]和[n/2+1, n-1];
三分查找将比较n/3和2n/3两个位置然后在三个区间比较
经过计算,二分查找最坏情况log2n,三分查找最坏情况2log3n,经过求导运算,可见还是二分好一些,加上二分比较简单,所以二分查找应用广泛。

二分查找的位运算优化(Update on 2020/2/3)

二分查找的mid = left + (right - left)/2表示还能优化。

由于位运算 >>1 或者 >>>1 基本等价于/2,但会更高效一些,所以可以这么写:mid = left + (right - left>>>1),简直666……

注意不是 >>>2 呀!

可看 >>>、>>、<< 辨析

Java整数数组标准二分查找(Update on 2020/2/9)

该版本的二分查找不是全数组查找,而是标定fromIndex和toIndex的,如果想改成全数组查找,只需包装一下这个方法,设置fromIndex=0, toIndex=array.length即可。

注意用到了位运算符 >>>,可提升效率。

注意用到了low + (high - low >>> 1),防爆int。

注意查找失败返回-(low + 1)。

private static int binarySearch(int[] array, int fromIndex, int toIndex, int key) { 
    int low = fromIndex;
    int high = toIndex - 1;
    while(low <= high) { 
        int mid = low + (high - low >>> 1);
        int midValue = array[mid];
        if (midValue < key) { 
            low = mid + 1;
        } else { 
            if (midValue <= key) { 
                return mid;
            }
            high = mid - 1;
        }
    }
    return -(low + 1);
}

二分查找也能递归(Update on 2020/2/9)

当然可以的,只不过一般用的是非递归的版本,感兴趣自己可以写写呀。

二分查找の开闭区间(Update on 2020/2/11)

我们不论是使用现成API的binarySearch()还是自己编写函数,二分查找的fromIndex和toIndex一般是有讲究的。
要记住:fromIndex取,toIndex不取
即——左闭右开
这是一种约定俗成的习惯写法,也有其背后的合理性,感兴趣的读者可以移步此处:
编程语言的区间为何常是左闭右开?

二分查找是一种线性的查找(Update on 2020/2/11)

学过数据结构与算法,我们就会知道,查找/搜索有很多很多的种类。
数据结构中提到的重要的查找有以下几种:

  • 线性查找
  • 树状查找
  • 哈希查找
  • 索引查找

其中,二分查找属于线性查找的门类。

对于树表等结构,二分查找找不到自己的“索引”,就没法进行下去了(当然,完全二叉树的结点是有索引的,不过没必要)。

二分查找与链表查找(Update on 2020/2/11)

这个问题啊,其实一般来说是不行的。
理由就是:二分查找之所以适合于数组/顺序表,是利用了其随机存取的特性。顺序存储的数据结构可以寻址随机访问,但链表这种链接存储的线性表,没办法直接按照索引去操作,故而没法使用二分查找。
(不过如果说非要用的话,也总有办法的~只是真的不必……)

二分查找也能优化(Update on 2020/2/11)

这里有我的一篇文章:线性表查找技术+树表查找技术,提到了特殊情况下可能更加优化的插值查找,可能有O(loglogN)的效率,感兴趣可以自行了解一下。

关于序列可变的顺序维护(Update on 2020/2/11)

如果说序列不能做到Python的元组那样,直接“可变”,那还要用二分查找的话就必须维护序列的有序性。

我们也说了,二分查找适合于随机访问的线性结构,但快排、归并这种“高效算法”反而显得没必要(没必要为了一个数据的增删就重新排一次NlogN)。顺序表这种存在,插入排序的调整需要大量调整,也不太好。

我的思考是,可以维护一个堆,利用堆排序来维护有序性。
由数据结构知识,堆是完全二叉树,所以可以建立随机访问的下标/索引,虽然建堆是NlogN的,但堆的一次调整不过是logN,只要维护好这样一个堆,通过一个顺序表结构来存储,就很合适。

这个Part完全是我自己的纯思考,也没太实践过,只能说谈谈思路罢了。

二分查找广义版(Update on 2020/2/25)

加上泛型,推广到AnyType,利用Comparable和compareTo()进行比较,利用数组存储有序数据,二分查找的思想实现高效查找。

public class BinarySearch { 

    private static final int NOT_FOUND = -1;

    /** * Performs the standard binary search. * @return index where item is found, or -1 if not found */
    public static <T extends Comparable<? super T>> int binarySearch(T[] array, T t) { 
        int low = 0, high = array.length - 1;
        while(low <= high) { 
            int mid = low + high >>> 1;
            if(array[mid].compareTo(t) < 0) { 
                low = mid + 1;
            } else if(array[mid].compareTo(t) > 0) { 
                high = mid - 1;
            } else { 
                return mid;
            }
        }
        return NOT_FOUND;
    }
    
}

测试

public class BinarySearchTest { 
    public static void main(String [] args) { 
        int size = 8;
        Integer[] array = new Integer[size];
        for(int i = 0; i < size; i++) { 
            array[i] = i * 2;
        }
        for(int i = 0; i < size * 2; i++) { 
            System.out.println("Found\t" + i + "\tat\t" + binarySearch(array, i));
        }
    }
}

测试结果

Found	0	at	0
Found	1	at	-1
Found	2	at	1
Found	3	at	-1
Found	4	at	2
Found	5	at	-1
Found	6	at	3
Found	7	at	-1
Found	8	at	4
Found	9	at	-1
Found	10	at	5
Found	11	at	-1
Found	12	at	6
Found	13	at	-1
Found	14	at	7
Found	15	at	-1
    原文作者:星拱北辰
    原文地址: https://blog.csdn.net/weixin_43896318/article/details/102293879
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。