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

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

P粉602998670

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

原创

300人浏览过

线性查找从头遍历数组比较元素，找到则返回索引，否则返回-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++免费学习笔记（深入）”；

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

网龙b2b仿阿里巴巴电子商务平台

本系统经过多次升级改造，系统内核经过多次优化组合，已经具备相对比较方便快捷的个性化定制的特性，用户部署完毕以后，按照自己的运营要求，可实现快速定制会费管理，支持在线缴费和退费功能财富中心，管理会员的诚信度数据单客户多用户登录管理全部信息支持审批和排名不同的会员级别有不同的信息发布权限企业站单独生成，企业自主决定更新企业站信息留言、询价、报价统一管理，分系统查看分类信息参数化管理，支持多样分类信息，

查看详情

实现逻辑：

设置左边界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中文网其它相关文章！