线性搜索算法(C++)详解
线性搜索(Linear Search)是一个非常简单的算法,有时也称为顺序搜索,它使用一个循环按顺序遍历一个数组,从第一个元素开始,它将每个元素与正在搜索的值进行比较,并在找到该值或遇到数组末尾时停止。如果正在搜索的值不在数组中,则算法将搜索到数组的末尾。
以下是执行线性搜索的函数的伪代码:
下列程序是一个使用 searchList 函数的完整程序。它搜索一个包含 5 个元素的 test 数组,以查找得分为 100 的项目。
但是,它的缺点是效率低下。如果要搜索的数组包含 20 000 个元素,则算法将不得不查看所有 20 000 个元素,以便找到存储在最后一个元素中的值或确定所需元素不在数组中。
在一个典型的案例中,一个项目在数组开头附近的位置被发现和在末尾附近被发现的可能性是差不多的。平均而言,对于 N 个项目的数组,线性搜索将需要
当线性搜索未能找到某个项目时,必须对该数组中的每个元素进行比较。随着搜索失败次数的增加,平均比较次数也会增加。所以,如果速度很重要,那么在可以避免的情况下,线性搜索不应该用于大型数组。
以下是执行线性搜索的函数的伪代码:
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)。当然,这是假定所搜索的项目在数组中必定存在的情况。当线性搜索未能找到某个项目时,必须对该数组中的每个元素进行比较。随着搜索失败次数的增加,平均比较次数也会增加。所以,如果速度很重要,那么在可以避免的情况下,线性搜索不应该用于大型数组。
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频