线性查找适用于无序数组，时间复杂度O(n)；二分查找效率高，时间复杂度O(log n)，但要求数组有序。
在c++中查找数组中的元素，最常用的方法是线性查找和二分查找。它们各有适用场景：线性查找适用于无序数组，时间复杂度为O(n)；二分查找效率更高，时间复杂度为O(log n)，但要求数组必须有序。
线性查找实现
线性查找从数组第一个元素开始，逐个比较，直到找到目标值或遍历完整个数组。
实现方式简单，不需要数组有序。
代码示例：
#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; // 未找到返回-1 }</p><p>int main() { int arr[] = {5, 3, 9, 1, 7}; int size = sizeof(arr) / sizeof(arr[0]); int target = 9; int result = linearSearch(arr, size, target);</p><div class="code" style="position:relative; padding:0px; margin:0px;"><pre class='brush:php;toolbar:false;'>if (result != -1) { cout << "元素 " << target << " 在索引 " << result << " 处找到。n"; } else { cout << "元素 " << target << " 未找到。n"; } return 0;
}
立即学习“C++免费学习笔记（深入）”；
二分查找实现
二分查找每次将查找区间缩小一半，前提是数组必须按升序或降序排列。
查找过程：比较中间元素与目标值，根据大小关系决定向左或向右继续查找。
代码示例（迭代方式）：
#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;
}
立即学习“C++免费学习笔记（深入）”；
int main() { int arr[] = {1, 3, 5, 7, 9}; // 必须有序 int size = sizeof(arr) / sizeof(arr[0]); int target = 7; int result = binarySearch(arr, size, target);
if (result != -1) { cout << "元素 " << target << " 在索引 " << result << " 处找到。n"; } else { cout << "元素 " << target << " 未找到。n"; } return 0;
}
立即学习“C++免费学习笔记（深入）”；
递归方式实现二分查找
二分查找也可以用递归方式实现，逻辑清晰，便于理解。
int binarySearchRecursive(int arr[], int left, int right, int target) { if (left > right) { return -1; } <pre class='brush:php;toolbar:false;'>int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { return binarySearchRecursive(arr, mid + 1, right, target); } else { return binarySearchRecursive(arr, left, mid - 1, target); }
}
立即学习“C++免费学习笔记（深入）”；
调用方式：binarySearchRecursive(arr, 0, size – 1, target);
基本上就这些。线性查找简单通用，二分查找高效但依赖有序。根据实际数据情况选择合适方法。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
