signed

QiShunwang

“诚信为本、客户至上”

数据结构与算法——二分查找和插值查找的算法

2020/8/19 22:38:23   来源:

二分查找

二分查找也称折半查找,它的前提是线性表中的记录必须是关键有序,线性表必须采用顺序存储。

算法描述:

  1. 如果待查序列不为空,则将它的中间元素与要查找的目标元素进行匹配,看它们是否相等;
  2. 如果相等,则返回该中间元素的索引,并退出算法;此时就查找成功了;如果不相等,就比较这两个元素的大小;
    a. 如果该中间元素大于目标元素,那么就将当前序列的前半部分作为新的待查序列;这是因为后半部分的所有元素都大于目标元素,它们全都被排除了。
    b. 如果该中间元素小于目标元素,那么就将当前序列的后半部分作为新的待查序列;这是因为前半部分的所有元素都小于目标元素,它们全都被排除了。
  3. 在新的待查序列上重新开始第1步的工作;直至区间元素个数为0

算法实现:


int binary_Search(int* arr, int n, int value) 
{
    int low, high, mid;
    low = 0;
    high = n;

    while (low <= high) 
    {
        mid = (low + high) / 2;

        if (arr[mid] < value) 
        {
            low = mid + 1;
        }
        else if (arr[mid] > value) 
        {
            high = mid - 1;
        }
        else 
        {
            return mid;
        }

        return -1;
    }
}

复杂度:

时间复杂度为:O(logn)

插值查找

插值查找(Interpolation Search)是根据要查找的关键字key与查找表中最大最小记录的关键字比较之后的查找方法,其核心就是在于插值的计算公式;插值查找是对二分查找的插值公式进行了改进:

将mid的值\frac{low + high}{2}修改为low+\frac{(high-low)*(key-R[low])}{R[high]-R[low]}

 

int InterpolationSearch(int* arr, int n, int value)
{
    int low, high, mid;
    low = 0;
    high = n;

    while (low <= high)
    {
        mid = low + (value - arr[low])*(high - low) / (arr[high] - arr[low]);

        if (arr[mid] < value)
        {
            low = mid + 1;
        }
        else if (arr[mid] > value)
        {
            high = mid - 1;
        }
        else
        {
            return mid;
        }

        return -1;
    }
}