线性查找从头遍历数组比较元素，找到则返回索引，否则返回-1；二分查找要求有序数组，通过比较中间值缩小范围，时间复杂度O(log n)，效率更高。
在c++中，数组查找常用的方法有线性查找和二分查找。线性查找适用于无序数组，时间复杂度为O(n)；二分查找效率更高，时间复杂度为O(log n)，但要求数组必须有序。下面分别介绍这两种方法的实现方式。
线性查找实现
线性查找从数组的第一个元素开始，逐个比较目标值与数组元素，直到找到匹配项或遍历完整个数组。
实现步骤：
- 遍历数组中的每一个元素
- 如果当前元素等于目标值，返回其索引
- 如果遍历结束仍未找到，返回-1表示未找到
示例代码：
#include <iostream> using namespace std; <p>int linearSearch(int arr[], int size, int target) { for (int i = 0; i < size; ++i) { if (arr[i] == target) { return i; // 返回找到的索引 } } return -1; // 未找到 }</p><p>int main() { int arr[] = {5, 3, 8, 1, 9, 2}; int size = sizeof(arr) / sizeof(arr[0]); int target = 1; int result = linearSearch(arr, size, target); if (result != -1) { cout << "元素在索引 " << result << " 处找到。" << endl; } else { cout << "元素未找到。" << endl; } return 0; }</p>
二分查找实现
二分查找通过不断缩小查找范围，每次将中间元素与目标值比较，决定向左或右继续查找。
立即学习“C++免费学习笔记（深入）”；
实现前提：数组必须是有序的（升序或降序）。
实现逻辑：
- 设置左边界left = 0，右边界right = size – 1
- 计算中间位置mid = left + (right – left) / 2（防止溢出）
- 比较arr[mid]与target
- 若相等，返回mid；若target更小，搜索左半部分；否则搜索右半部分
- 重复直到left
示例代码：
#include <iostream> using namespace std; <p>int binarySearch(int arr[], int size, int target) { int left = 0; int right = size - 1;</p><pre class='brush:php;toolbar:false;'>while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; // 未找到
}
int main() { int arr[] = {1, 2, 3, 5, 8, 9}; // 有序数组 int size = sizeof(arr) / sizeof(arr[0]); int target = 5; int result = binarySearch(arr, size, target); if (result != -1) { cout << “元素在索引 ” << result << ” 处找到。” << endl; } else { cout << “元素未找到。” << endl; } return 0; }
使用STL中的查找方法
C++标准库提供了便捷的查找函数，可简化代码。
- std::find：用于线性查找，适用于任意数组或容器
- std::binary_search：判断元素是否存在（返回bool）
- std::lower_bound：返回第一个不小于target的迭代器，可用于获取索引
示例代码：
#include <iostream> #include <algorithm> using namespace std; <p>int main() { int arr[] = {1, 2, 3, 5, 8, 9}; int size = sizeof(arr) / sizeof(arr[0]); int target = 5;</p><pre class='brush:php;toolbar:false;'>// 使用 binary_search 判断是否存在 bool found = binary_search(arr, arr + size, target); if (found) { cout << "元素存在。" << endl; } // 使用 lower_bound 获取索引 int* pos = lower_bound(arr, arr + size, target); if (*pos == target) { cout << "索引为：" << (pos - arr) << endl; } return 0;
}
基本上就这些。线性查找简单直接，适合小数组或无序数据；二分查找效率高，适合大而有序的数组。根据实际需求选择合适的方法。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
