线性搜索算法(C++)详解
C++ 详解 线性 搜索算法
2023-06-13 09:11:59 时间
线性搜索(Linear Search)是一个非常简单的算法,有时也称为顺序搜索,它使用一个循环按顺序遍历一个数组,从第一个元素开始,它将每个元素与正在搜索的值进行比较,并在找到该值或遇到数组末尾时停止。如果正在搜索的值不在数组中,则算法将搜索到数组的末尾。
以下是执行线性搜索的函数的伪代码:
Set found to false Set position to -1 Set index to 0 While index number of elements and found is false If list[index]is equal to search value found = true position = index End If Add 1 to index End While Return position
下面的函数 searchList 是一个 C++ 代码的示例,用于对一个整数数组执行线性搜索。数组 list 最多具有 size 个元素,以下语句将搜索它是否出现了存储在 value 中的数字。如果找到该数字,则返回其数组下标。否则,返回 -1,表示该值没有出现在数组中。
int searchList(const int list[], int size, int value) int index = 0; //用作搜索数组的下标 int position = -1; //用于记录搜索值的位置 bool found = false; //指示值是否找到的标记 while (index size !found) if (list [index] == value) // 如果找到该值 found = true; // 设置标记 position = index; //记录值的下标 index++; //转到下一个元素 return position; // 返回该位置或-1 }
注意,-1 被选作表示在数组中找不到搜索值的原因是:-1 不是有效的下标。其实,任何其他非有效的下标值也可以用来指示这一点。
下列程序是一个使用 searchList 函数的完整程序。它搜索一个包含 5 个元素的 test 数组,以查找得分为 100 的项目。
// This program demonstrates the searchList function,which performs a linear search on an integer array. #include iostream using namespace std; // Function prototype int searchList(const int [], int, int); const int SIZE = 5; int main() int tests[SIZE] = {87, 75, 98, 100, 82}; int results; // Holds the search results // Search the array for the value 100 results = searchList(tests, SIZE, 100); //If searchList returned -1, 100 was not found if (results == -1) cout You did not earn 100 points on any test./n else // Otherwise results contains the subscript of the first 100 found in the array cout You earned 100 points on test cout (results +1) ./n return 0; int searchList(const int list[], int size, int value) int index =0; // Used as a subscript to search array int position = -1; // Used to record position of search value bool found = false; // Flag to indicate if the value was found while (index size !found) if (list[index] == value)// If the value is found found = true; // Set the flag position = index; // Record the value s subscript index++; // Go to the next element return position; // Return the position, or -1 }
程序输出结果:
You earned 100 points on test 4.
线性搜索的效率缺陷线性搜索的优点是简单,它很容易理解和实施。此外,它不要求数组中的数据以任何特定顺序存储。
但是,它的缺点是效率低下。如果要搜索的数组包含 20 000 个元素,则算法将不得不查看所有 20 000 个元素,以便找到存储在最后一个元素中的值或确定所需元素不在数组中。
在一个典型的案例中,一个项目在数组开头附近的位置被发现和在末尾附近被发现的可能性是差不多的。平均而言,对于 N 个项目的数组,线性搜索将需要 N/2 次尝试才能找到项目。如果一个数组有 20 000 个元素,则线性搜索平均需要对 10 000 个元素进行比较(N/2 是平均比较次数,最大比较次数总是 N)。当然,这是假定所搜索的项目在数组中必定存在的情况。
当线性搜索未能找到某个项目时,必须对该数组中的每个元素进行比较。随着搜索失败次数的增加,平均比较次数也会增加。所以,如果速度很重要,那么在可以避免的情况下,线性搜索不应该用于大型数组。
22110.html
cgohtml相关文章
- EasyC++11,常用字符串函数大全
- C++11 语言特性之原始字符串(Raw String Literals)
- LeetCode82. 删除排序链表中的重复元素 II(c++详解)
- C++ 中文周刊 第83期
- C++教程系列之-01-C++概述与NOIP案例
- 在 C++ 中标记字符串与getline() 函数和字符数组
- C++智能指针详解(共享指针,唯一指针,自动指针)
- C++为什么能重夺年度语言?
- C++三大特性之封装详解编程语言
- C++ 友元类使用 (friend)详解编程语言
- C/C++中可变参数函数的实现详解编程语言
- C++转换构造函数(详解版)
- C++实现可变长度的动态数组
- C++类模板(模板类)与友元详解
- C++ unordered_multimap用法详解
- C++ set添加、删除和访问(STL set添加、删除和访问)元素详解
- C++ upper_bound(STL upper_bound)二分查找算法详解
- C++线性同余法生成随机数(linear_congruential_engine)用法详解
- C++ cin.getline用法详解
- C++ string支持迭代器方法详解
- C++左值和右值(详解版)
- C++多态和虚函数详解
- C++写注册表项实例
- C++中拷贝构造函数的应用详解
- C++结构体用法实例分析