折半查找和插值查找

ilovealt

关注

发布于: 2020 年 11 月 24 日

定义

折半查找（Binary Search）定义：又称二分查找，有序的顺序存储线性表（通常从小到大）。

时间复杂度：O(logn)；

核心计算公式：mid = low+1/2(high-low)；

基本思路：取中间值与给定值进行比较

等于查找成功（终止）；

大于在左半区继续找；

小于在右半区继续找；

重复上述过程，直到查找成功，或者查询所有无此记录，查找失败。

插值查找定义：类似折半查找，只是查询比例不同。

时间复杂度：O(logn)；

核心计算公式：mid = low+(high-low)*(key-a[low])/(a[high]-a[low])；

对比：这两个方式的查找唯一区别就是 mid 的计算方法。

代码

折半查找代码：

#include <stdio.h>
#define MAXSIZE 100 /*存储空间初始分配量*/
/*折半查找*/int Binary_Search(int *a, int n, int key){    int low,high,mid;    low = 1;    high = n;    while (low <= high)    {        mid = low + (high-low)/2;        if(a[mid] > key)        {            high = mid - 1;        } else if (a[mid] < key)        {            low = mid + 1;        } else        {            return mid;        }       }    return 0;}
int main() {    int result;    int arr[MAXSIZE]={0,1,16,24,35,47,59,62,73,88,99};
    result = Binary_Search(arr, 10, 62);    printf("Binary_Search:%d \n", result);
    return 0;}

复制代码

插值查找代码：

#include <stdio.h>
#define MAXSIZE 100 /*存储空间初始分配量*/
/*插值查找*/int Interpolation_Search(int *a, int n, int key){    int low,high,mid;    low = 1;    high = n;    while (low <= high)    {        mid = low + (high-low)*(key - a[low])/(a[high] - a[low]);        if(a[mid] > key)        {            high = mid - 1;        } else if (a[mid] < key)        {            low = mid + 1;        } else        {            return mid;        }        }    return 0;}
int main() {    int result;    int arr[MAXSIZE]={0,1,16,24,35,47,59,62,73,88,99};
    result = Interpolation_Search(arr, 10, 62);    printf("Interpolation_Search:%d \n", result);
    return 0;}

复制代码

成长快乐！成长快乐！成长快乐！

发布于: 2020 年 11 月 24 日阅读数: 34

原文链接:【http://xie.infoq.cn/article/6350303f51d409297b0b82e7e】。

ilovealt

关注

不忘初心，方得始终！ 2018.05.02 加入

When you feel like giving up,remember why you held on so long in the first place.

发布

暂无评论

创作场景

折半查找和插值查找

定义

代码

ilovealt

评论