二分搜索
课上练习
知识总结
二分查找-知识总结
二分搜索-知识总结 基本概念 二分搜索（Binary Search）是一种高效的搜索算法，用于在有序数组中查找特定元素。它通过逐步缩小查找范围来实现较低的时间复杂度。以下是二分搜索的基本概念、步骤、复杂度分析，以及实现示例。 前提条件：二分搜索只能在有序的数组或列表中使用。 工作原理：通过比较目标值与中间元素的大小关系，决定在数组的哪一半中继续搜索，逐步缩小查找范围，直到找到目标元素或范围为空。 效率高：与线性搜索相比，二分搜索的查找速度更快，特别是在处理大型数据集时。 限制条件：要求数组是有序的。如果数据无序，需要先排序，这可能会增加额外的时间开销。
算法步骤 初始化边界：设定两个指针，left 和 right，分别指向数组的起始位置和结束位置。 计算中点：计算中点索引 mid，通常使用公式 mid = left + (right - left) / 2 以避免潜在的整数溢出。 比较中点值： 如果 a[mid] 等于目标值 target，则返回中点索引。 如果 a[mid] 小于 target，则将 left 更新为 mid + 1，继续在右半部分查找。 如果 a[mid] 大于 target，则将 right 更新为 mid - 1，继续在左半部分查找。 循环终止：当 left 超过 right 时，表示未找到目标值。 时间复杂度 时间复杂度：O(logn)O(\log n)O(logn)，每次操作都会将搜索范围缩小一半。 空间复杂度：O(1)O(1)O(1)，只使用了常数级别的额外空间。
适用场景 查找有序数据中的特定值。 求解具有单调性问题（如最小化、最大化问题）。 实现高效的动态数据结构（如平衡二叉搜索树中的操作）。
代码示例
1#include <iostream>
2#include <vector>
3using namespace std;
4
5int binarySearch(const vector<int>& nums, int target) {
6 int left = 0;
7 int right = nums.size() - 1;
8
9 while (left <= right) {
10 int mid = left + (right - left) / 2;
11
12 if (nums[mid] == target) {
13 return mid; // 找到目标值，返回索引
14 } else if (nums[mid] < target) {
15 left = mid + 1; // 目标值在右半部分
16 } else {
17 right = mid - 1; // 目标值在左半部分
18 }
19 }
20
21 return -1; // 未找到目标值，返回-1
22}
23
24int main() {
25 vector<int> nums = {1, 3, 5, 7, 9, 11};
26 int target = 7;
27
28 int result = binarySearch(nums, target);
29 if (result != -1) {
30 cout << "Element found at index " << result << endl;
31 } else {
32 cout << "Element not found" << endl;
33 }
34
35 return 0;
36}️课后作业
☝️总结作业
总结作业非常重要，请务必认真完成✔️
- 二分查找的核心思想是什么？
- 二分查找的时间复杂度是多少？
- 简单介绍二分查找的工作原理。
✌️编程作业
考试只有一次提交机会，请务必本地检查正确后再提交❇️