C++实现顺序查找，折半查找，插值查找

1.顺序查找

从数组起始扫描到数组结尾，判断该索引数组是否和关键字相等，成功返回1

代码如下：

//顺序查找

int seqSearch(int *array, int low, int high, int key)

{

    for (int i = low; i < high; i++)

    {

        if (array[i] == key)

            return i;

    }

    return -;

}

2.折半查找

适用于有序数组

不停地抛弃掉一半的结点，例子如下

我们要查找key=4的结点，获取中间值mid，mid=(low+high)/2，所以mid=(1+7)/2=4，发现4小于10，则可以锁定key的位置在mid的左侧，此时使mid减一

mid=(1+3)/2=2，我们发现4依然小于8，则锁定key的区域在mid左边，mid再减一

此时low=high=1，所以mid=1，以mid为索引的数组正好等于4，找到key，返回成功

代码如下：

//折半查找(只适用于已经排序好的)

int binarySearch(int *array, int low, int high, int key)

{

    while (low <= high)

    {

        //从中间划分

        //mid如果不是整数，则直接向下取整，不会影响查找结果

        int mid = (low + high) / ;

        //正好是中间这个数

        if (key == array[mid])

            return mid;

        //数比中间的数大，则在后半部分再切一刀缩小范围

        else if (key > array[mid])

            low = mid + ;

        //数比中间的数小，则在前半部分再切一刀缩小范围

        else

            high = mid - ;

    }

    return -;

}

3.插值查找

适用于有序数组

优化中点mid的选择，逻辑和折半查找一致，以更科学的mid点划分左右区域

//插值查找(只适用于已经排序好的)

//和折半查找逻辑一致，修改了mid值

int interpolationSearch(int *array, int low, int high, int key)

{

    while (low <= high)

    {

        //优化中间值

        int mid = low+(key-array[low])/(array[high]-array[low])*(high - low-);

        //正好是中间这个数

        if (key == array[mid])

            return mid;

        //数比中间的数大，则在下半部分再切一刀缩小范围

        else if (key > array[mid])

            low = mid + ;

        //数比中间的数小，则在上半部分再切一刀缩小范围

        else

            high = mid - ;

    }

    return -;

}

4.代码汇总+测试

#include<stdlib.h>

#include<iostream>

using namespace std;

int seqSearch(int *array, int low, int high, int key);

int binarySearch(int *array, int low, int high, int key);

int interpolationSearch(int *array, int low, int high, int key);

int main(void)

{

    int * array = new int[];

    int low = ;

    int high = ;

    array[] = ;

    array[] = ;

    array[] = ;

    array[] = ;

    array[] = ;

    array[] = ;

    array[] = ;

    int seqResult = seqSearch(array,low,high,);

    cout << "顺序查找结果是：" << seqResult << endl;

    int binaryResult = binarySearch(array, low, high,);

    cout << "折半查找结果是：" << binaryResult << endl;

    int interpolationResult = interpolationSearch(array, low, high, );

    cout << "插值查找结果是：" << interpolationResult << endl;

    delete array;

    system("pause");

    return ;

}

//顺序查找

int seqSearch(int *array, int low, int high, int key)

{

    for (int i = low; i < high; i++)

    {

        if (array[i] == key)

            return i;

    }

    return -;

}

//折半查找(只适用于已经排序好的)

int binarySearch(int *array, int low, int high, int key)

{

    //0 3 5 6 9 11 13 15

    while (low <= high)

    {

        //从中间划分

        //mid如果不是整数，则直接向下取整，不会影响查找结果

        int mid = (low + high) / ;

        //正好是中间这个数

        if (key == array[mid])

            return mid;

        //数比中间的数大，则在后半部分再切一刀缩小范围

        else if (key > array[mid])

            low = mid + ;

        //数比中间的数小，则在前半部分再切一刀缩小范围

        else

            high = mid - ;

    }

    return -;

}

//插值查找(只适用于已经排序好的)

//和折半查找逻辑一致，修改了mid值

int interpolationSearch(int *array, int low, int high, int key)

{

    //0 3 5 6 9 11 13 15

    while (low <= high)

    {

        //优化中间值

        int mid = low+(key-array[low])/(array[high]-array[low])*(high - low-);

        //正好是中间这个数

        if (key == array[mid])

            return mid;

        //数比中间的数大，则在下半部分再切一刀缩小范围

        else if (key > array[mid])

            low = mid + ;

        //数比中间的数小，则在上半部分再切一刀缩小范围

        else

            high = mid - ;

    }

    return -;

}

巴特西

C++实现顺序查找，折半查找，插值查找

1.顺序查找

2.折半查找

3.插值查找

4.代码汇总+测试

最新文章

热门文章