查找算法总结
🧑💻 作者: 一可爱小白兔
📦 版本: 1.0.0
📄 字数(字): 0
⏳ 时长(min): 0
📅 发表于: 2025-04-18
⏱️ 更新于: 2026-01-30
线性查找
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(1)
二分查找（折半查找）
复杂度
- 时间复杂度：O(log n)
- 空间复杂度：
- 递归：O(log n)
- 非递归：O(1)
拓展
查找排序数组中第一个等于给定值元素的位置
cpp
int find_first_target(vector<int> &nums, int target) {
int left = 0, right = nums.size();
int ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
cpp
auto low = lower_bound(nums.begin(), nums.end(), target);
if(low != nums.end() && *low == target)
return low - nums.begin();1
2
3
2
3
查找排序数组中最后一个等于给定值元素的位置
cpp
int find_last_target(vector<int> &nums, int target) {
int left = 0, right = nums.size();
int ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
cpp
auto up = upper_bound(nums.begin(), nums.end(), target);
if(up != nums.begin())
return up - nums.begin() - 1;1
2
3
2
3
LeetCode
- 704. 二分查找
- 35. 搜索插入位置 ❤️❤️❤️ 为什么不存在的target返回left?
- 34. 在排序数组中查找元素的第一个和最后一个位置