七叶笔记 » java编程 » 算法系列15天速成 第四天 五大经典查找【上】

算法系列15天速成 第四天 五大经典查找【上】

折半查找: 这种查找很有意思,就是每次都砍掉一半,

             比如"幸运52“中的猜价格游戏,价格在999元以下,1分钟之内能猜到几样给几样,如果那些选手都知道折半查找,             那结果是相当的啊。

不过要注意,这种查找有两个缺点:

            第一: 数组必须有序,不是有序就必须让其有序,大家也知道最快的排序也是NLogN的,所以.....呜呜。            第二: 这种查找只限于线性的顺序存储结构。

上代码:

先前也说过,查找有一种形态是破坏性的,那么对于线性结构的数据来说很悲惨,因为每次破坏一下,

可能都导致数组元素的整体前移或后移。

    所以线性结构的查找不适合做破坏性操作,那么有其他的方法能解决吗?嗯,肯定有的,不过要等下一天分享。

ps:  线性查找时间复杂度:O(n);         折半无序(用快排活堆排)的时间复杂度:O(NlogN)+O(logN);         折半有序的时间复杂度:O(logN);

相关文章