C++数组查找方法线性二分查找实现-C++-PHP中文网

C++数组查找方法线性二分查找实现

P粉602998670

发布： 2025-08-26 11:48:02

原创

297人浏览过

线性查找从头遍历数组比较元素，找到则返回索引，否则返回-1；二分查找要求有序数组，通过比较中间值缩小范围，时间复杂度O(log n)，效率更高。

c++数组查找方法线性二分查找实现

在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++免费学习笔记（深入）”；

实现前提：数组必须是有序的（升序或降序）。

腾讯智影-AI数字人

基于AI数字人能力，实现7*24小时AI数字人直播带货，低成本实现直播业务快速增增，全天智能在线直播

查看详情

实现逻辑：

设置左边界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;

登录后复制

}

基本上就这些。线性查找简单直接，适合小数组或无序数据；二分查找效率高，适合大而有序的数组。根据实际需求选择合适的方法。

以上就是C++数组查找方法线性二分查找实现的详细内容，更多请关注php中文网其它相关文章！