算法-01-二分查找/插值查找

一.顺序查找

在链表中常用，适合用来解决小规模数据，比较灵活简便。当数据较多时非常不推荐，查询速度非常慢。

二. 二分查找

2.1 二分查找简介：

通过将一组有序数据不断地分成两部分以缩小查询区间的查询方法
使用条件：数据有序

2.2二分查找的特点：

二分查找法优点是比较次数少，查找速度快，平均性能好，占用系统内存较少

2.3 二分查找的查询方式及其原理：

二分查找的查询步骤：

步骤一：检查表中间数据是否是目标数据，不是则继续向下执行
步骤二：利用中间位置记录将表分成前、后两个子表，如果中间位置记录的数据大于目标数据，则查找前一子表，否则查找后一子表
步骤三：重复以上过程，直到找到满足条件的数据，或直到子表不存在为止，则查找不成功

二分查找的查询原理：

下面举一个简单的例子，和此例的查找过程的流程图

问题：
一个含有10个元素的有序数组Array
Array的元素为：2，3，9，15，30，42，47，53，86，100
查找Array数组，确定47是否在数组中，若在数组中，返回其在数组中的位置

二分法查找过程：

2.4 二分查找实现：

方式一：使用while循环实现

template <typename Type>
int ArrayList<Type>::BinarySearch(Type x) {
    int min = 0;
    int max = currentsize;
    int mid = min + (max - min) / 2;
    cout << mid << endl;
    //注意这里是小于等于，没有等于号会出现重大错误
    while (min <= max)
    {
        if (elements[mid] == x) {
            cout << "目标元素是顺序表中的第" << mid+1 << "个元素" << endl;
            return mid;
        } 
        else if (elements[mid] < x) {
            min = mid + 1 ;
            mid = min + (max - min) / 2;
            cout << mid << endl;
        }
        else if (elements[mid] > x) {
            max = mid - 1 ;
            mid = min + (max - min) / 2;
            cout << mid << endl;
        }
    }
    cout << "目标元素不在顺序表中" << endl;
    return -1;

}

测试方法即执行结果：

int main() {
    //定义一个顺序表
    ArrayList<int> test(7);
    //创建一个有序数组
    int array[7] = {1,2,3,4,5,6};
    //将数组中的值拷贝到顺序表中
    for (int i = 0; i < 6; i++){
        test.Insert(array[i],i);
    }
    test.Print();

    //分别查询3，6，1，5，4
    test.InterpolateSearch(3);
    test.InterpolateSearch(6);
    test.InterpolateSearch(1);
    test.InterpolateSearch(5);
    test.InterpolateSearch(4);

    //程序暂停
    cin.get();
    return 0;
}

执行结果：

方式二：使用递归实现

template <typename Type>
int ArrayList<Type>::BinarySearch(Type x,int min,int max) {
    int mid = min + (max - min) / 2;
    if(elements[mid] == x){
        cout << "目标元素是顺序表中的第" << mid+1 << "个元素" << endl;
        return mid;
    }else if(elements[mid] < x){
        BinarySearch(x ,mid+1 ,max);
    }else if(elements[mid] > x){
        BinarySearch(x ,min ,mid-1);
    }
    cout << "目标元素不在顺序表中" << endl;
    return -1;

}

三. 插值查找

在二分查找的基础上做了改进，比二分查找的速度更快

3.1 插值查找对二分查找的改进：

二分查找是每次将目标区域缩小二分之一，而插值查找通过修改比例，每次查找将目标区域缩小缩小了更多
插值查找在实现方式上与二分查找的不同体现在mid中值的确定方面：
二分查找：

mid = min + (max - min) / 2;

插值查找：

mid = min + (max - min)*1.0*(x - elements[min]) / (elements[max] - elements[min]);

注意：由于C/C++的int类型的截断取整特性，所以在乘以比例之前先要乘以浮点数1.0

3.2 插值查找的循环方式实现：

//插值查找
template <typename Type>
int ArrayList<Type>::InterpolateSearch(Type x) {
    int min = 0;
    int max = currentsize;
    int mid = min + (max-min)/2;
    cout << mid << endl;
    while (min <= max)
    {
        if (elements[mid] == x) {
            cout << "目标元素是顺序表中的第" << mid + 1 << "个元素" << endl;
            return mid;
        }
        else if (elements[mid] < x) {
            min = mid + 1;
            mid = min + (max - min)*1.0*(x - elements[min]) / (elements[max] - elements[min]);
            cout << mid << endl;
        }
        else if (elements[mid] > x) {
            max = mid - 1;
            mid = min + (max - min)*1.0*(x - elements[min]) / (elements[max] - elements[min]);
            cout << mid << endl;
        }
    }
    cout << "目标元素不在顺序表中" << endl;
    return -1;
}