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]。

接下来,循环执行以下两步。

  1. 计算中点索引m = [(i+j)/2]
  2. 判断nums[m] 和 target的大小关系,分为以下三种情况。 a. 当num[m] < targe时,说明targe在区间[m + 1, j]中,因此执行i = m + 1 b. 当num[m] > targe时,说明targe在区间[i, m - 1]中,因此执行j = m - 1 a. 当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;
}