线性查找从头遍历数组比较元素，找到则返回索引，否则返回-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;}
基本上就这些。线性查找简单直接，适合小数组或无序数据；二分查找效率高，适合大而有序的数组。根据实际需求选择合适的方法。
