C/C++程序设计常用算法——查找算法

文档声明：
以下资料均属于本人在学习过程中产出的学习笔记，如果错误或者遗漏之处，请多多指正。并且该文档在后期会随着学习的深入不断补充完善。

资料仅供学习交流使用。
作者：Aliven888

1、简述

程序设计的关键就是算法，算法简单来说就是程序设计时问题解题步骤或者数据数据的流程。这里我们将介绍以下几种常用的算法：迭代法、穷举法、递推法、递归发、回溯法、贪婪法、查找算法、排序算法。

本章节主要介绍查找算法。

2、查找算法

查找算法：这里我们介绍两种比较常见的查找算法：顺序查找和二分查找。

2.1、顺序查找

顺序查找：一般用于在数组（或者链表）中查找指定的某个元素（或者节点）。要查找的数据一般称为关键字，顺序查找就是将给定的目标值逐个与数组元素（或者链表节点）进行比较，如果有与目标值相同的数组元素（或者链表节点），则查找成功并输出关键信息，否则认为查找失败，没有与目标值相同的元素（或者节点）。

特点：
适用于在无序的数据集合中查找目标值。缺点就是在找到目标值之前要把其他所有值遍历一遍。

代码实例：

int onFindValuePos(int iList[], int iLen, int key)
{
    int iRet = -1;

    for (size_t i = 0; i < iLen; i++)
    {
        if (key == iList[i])
        {
            iRet = i;
            break;
        }
    }

    return iRet;
}

int main()
{
    int iList[] = {1,2,3,4,5};
    int iLen = 5;
    int key = 3;
    cout << "3 pos is [" << onFindValuePos(iList, iLen, key) << "]" << endl;

    system("pause");
    return 0;
}

运行结果：

运行结果

2.2、二分查找

二分查找：数据集合一般是有序的，如果不是有序的，在使用二分法之前需要先进行排序。

二分法思想：

把查找范围对半分为两部分。
比对目标值与中间数据的大小，判断该目标值属于前半部分还是后半部分。
对目标值所属的部分在分为两部分，然后再将该目标值与此时的中间值对比，找对当前所属的部分，然后依次往复，直到遍历完数据集合或者找到目标值所在的位置（最后一个分割，两部分长度都为1表示执行完成）。

代码实例：

int onFindValuePos(int iList[], int iLen, int key)
{
    int iRet = -1;
    int iFront = 0;
    int iTail = iLen - 1;
    int iMid = 0;

    while (iFront <= iTail)
    {
        iMid = (iTail + iFront) / 2;
        if (key == iList[iMid])
        {
            iRet = iMid;
            break;
        }
        else if(key < iList[iMid])
        {
            iTail = iMid - 1;
        }
        else
        {
            iFront = iMid + 1;
        }
    }

    return iRet;
}

int main()
{
    int iList[] = {1,2,3,4,5,6,7,8,9};
    int iLen = 9;
    int key = 5;
    cout << "5 pos is [" << onFindValuePos(iList, iLen, key) << "]" << endl;

    system("pause");
    return 0;
}

运行结果：

运行结果

最后编辑于：2020.10.02 16:00:29