hello算法之二分查找
创建时间: 2026-05-03 16:29:07
二分查找
二分查找是基于分治策略的高效搜索算法。它利用数据的有序性,每轮搜索缩小一半的范围,直到查找到目标为止。
auto arr = {1, 3, 6, 8, 12, 15, 23, 26, 31, 35};
上面的数组,我们初始化指针i = 0和j = n - 1,分别表示指向数组的首元素和尾元素,代表搜索区间[0, n - 1]。
接下来,循环执行以下两步。
- 计算中点索引
m = [(i+j)/2] - 判断
nums[m]和target的大小关系,分为以下三种情况。 a. 当num[m] < targe时,说明targe在区间[m + 1, j]中,因此执行i = m + 1b. 当num[m] > targe时,说明targe在区间[i, m - 1]中,因此执行j = m - 1a. 当num[m] = targe时,说明找到targe,因此返回索引m。
若数组不包含目标元素,搜索区间最终会缩小为空。此时返回-1。
注意的是,由于i和j都是int类型,因此i + j计算的值可能会超出int类型的取值范围,因此为了避免越界,我们通常采用公示m = [i + (j-i)/2]来计算终点。
int binarySearch(vector<int> &nums, int target) {
int i = 0, j = nums.size() - 1;
for(;i <= j;) {
int m = i + (j - i) / 2;
if (nums[m] < target) {
i = m + 1;
}else if (nums[m] > target) {
j = m - 1;
} else
return m;
}
// 未找到元素
return -1;
}
