愿你坚持不懈,努力进步,进阶成自己理想的人

—— 2017.09, 写给3年后的自己

二分查找与插值查找

二分查找,又叫做折半查找。是针对有序表进行查找的一种算法,要使用二分查找,需要满足:
1、表是一个有序表(数据要是有序的)
2、表采用的顺序存储

算法实现

二分查找每次都是取一个范围内的中间值,让待查找关键字和中间值进行比较,如果较小,则缩小范围到中间值的左边范围,如果较大,则缩小范围到中间值的右边范围

function binarySearch($arr, $key) {
    $n = count($arr);
    $low  = 0;
    $high = $n-1;
    while($low <= $high) {
        $mid = intval( ($low+$high)/2 );
        if($key < $arr[$mid]) {
            $high = $mid-1;
        } elseif($key > $arr[$mid]) {
            $low = $mid+1;
        } else {
            return $mid;
        }
    }

    return -1;
}

C++实现:

int binarySearch(int arr[], int n, int key) {
    int low  = 0;
    int high = n-1;
    int mid;
    while(low <= high) {
        mid = (low+high)/2;
        if(key < arr[mid]) {
            high = mid-1;
        } else if(key > arr[mid]) {
            low = mid+1;
        } else {
            return mid;
        }
    }

    return -1;
}

算法的最佳情况时间复杂度为O(1),最差情况时间复杂度为O(logn),平均时间复杂度为O(logn)

插值查找

我们在使用二分查找的时候,会有一个问题:为什么一定是要二分,不能是四分、八分吗?
而且,打个比方,如果我们要在字典中查找zoo这个单词,我们一般的做法都会是直接翻到字典的最后面,而不是从中间翻开。而插值查找则与此类似,它是一种有目的的查找

  • 在二分查找中,mid = (low+high)/2,我们可以对这个公式做个变形,得到mid = (low+high+low-low)/2 = (2low + high-low)/2 = low + 1/2*(high-low),而插值查找,要优化的就是这个1/2
  • 插值查找中的计算方案,是使得mid = low + k(high-low),k的计算方式为(key-a[low])/(a[high]-a[low])

如此一来,我们进行查找的时候,就会根据数据的分布情况来计算出更适宜的定位目标。虽然插值查找的时间复杂度也是O(logn),但是 对于表长较长,关键字分布比较均匀的表而言,插值查找算法的性能要好得多。但如果数组数据分布比较极端,如{1,2,2000,2001,999999,9999999}这种不均匀数据,插值查找未必比较优秀