查找算法的作用是在给定的数据集合中搜索目标元素或确定目标元素是否存在。它可以帮助我们快速地找到所需的数据,提供有效的数据访问和处理方式。
常用的查找算法有以下几种:
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
// 线性查找
int linearSearch(const std::vector<int>& arr, int target) {
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == target) {
return i;
}
}
return -1; // 没有找到目标元素
}
// 二分查找(针对已排序数组)
int binarySearch(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
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 hashTableSearch(const std::unordered_map<int, int>& table, int target) {
auto it = table.find(target);
if (it != table.end()) {
return it->second;
}
return -1; // 没有找到目标元素
}
int main() {
std::vector<int> arr = {10, 25, 4, 15, 8, 36};
// 线性查找
int target1 = 15;
int index1 = linearSearch(arr, target1);
if (index1 != -1) {
std::cout << "线性查找:" << target1 << " 的索引为 " << index1 << std::endl;
} else {
std::cout << "线性查找:没有找到 " << target1 << std::endl;
}
// 二分查找前需要将数组排序
std::sort(arr.begin(), arr.end());
// 二分查找
int target2 = 25;
int index2 = binarySearch(arr, target2);
if (index2 != -1) {
std::cout << "二分查找:" << target2 << " 的索引为 " << index2 << std::endl;
} else {
std::cout << "二分查找:没有找到 " << target2 << std::endl;
}
// 哈希表查找
std::unordered_map<int, int> table;
for (int i = 0; i < arr.size(); i++) {
table[arr[i]] = i;
}
int target3 = 8;
int index3 = hashTableSearch(table, target3);
if (index3 != -1) {
std::cout << "哈希表查找:" << target3 << " 的索引为 " << index3 << std::endl;
} else {
std::cout << "哈希表查找:没有找到 " << target3 << std::endl;
}
return 0;
}
编译运行:
g++ -o main main.cpp && ./main
线性查找:15 的索引为 3
二分查找:25 的索引为 4
哈希表查找:8 的索引为 1