数据结构与算法整理总结---二分查找

⼆分查找针对的是⼀个有序的数据集合,查找思想有点类似分治思想。每次都通过跟区间的中间元素对⽐,将待查找的区间缩⼩为之前的⼀半,直到找到要查找的元素,或者区间被缩⼩为0。

⼆分查找是⼀种⾮常⾼效的查找算法,我们假设数据⼤⼩是n,每次查找后数据都会缩⼩为原来的⼀半,也就是会除以2。最坏情况下,直到查找区间被缩⼩为空, 才停⽌。

数据结构与算法整理总结---二分查找

可以看出来,这是⼀个等⽐数列。其中n/2k=1时,k的值就是总共缩⼩的次数。⽽每⼀次缩⼩操作只涉及两个数据的⼤⼩⽐较,所以,经过了k次区间缩⼩操作,时间复杂度就是O(k)。通过n/2k=1,我们可以求得k=log2n,所以时间复杂度就是O(logn)。

<?php
    $arr = [0,4,6,8,23,45,54,88,123];
    function search($array,$low,$high,$value){
        if($low>$high){
            return false;
        }
        $mid = ($low+$high)/2;
        if($arr[$mid] == $value){
            return $mid;
        }else if($arr[$mid]<$value){
            return search($array,$mid+1,$high,$value);
        }else{
            return search($array,$low,$mid-1,$value);
        }
    }
    search($arr,0,count($arr),23);

⼆分查找应⽤场景的局限性

⼆分查找依赖的是顺序表结构,简单点说就是数组。

那⼆分查找能否依赖其他数据结构呢?⽐如链表。答案是不可以的,主要原因是⼆分查找算法需要按照下标随机访问元素。我们在数组和链表那两节讲过,数组按照下标随机访问数据的时间复杂度是O(1),⽽链表随机访问的时间复杂度是O(n)。所以,如果数据使⽤链表存储,⼆分查找的时间复杂就会变得很⾼。

⼆分查找针对的是有序数据。

⼆分查找对这⼀点的要求⽐较苛刻,数据必须是有序的。如果数据没有序,我们需要先排序。

数据量太⼩不适合⼆分查找

如果要处理的数据量很⼩,完全没有必要⽤⼆分查找,顺序遍历就⾜够了。

数据量太⼤也不适合⼆分查找

⼆分查找的底层需要依赖数组这种数据结构,⽽数组为了⽀持随机访问的特性,要求内存空间连续,对内存的要求⽐较苛刻。

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!