Binary Search 二分查找

Binary Search 二分查找

二分查找也称折半查找,它是一种效率较高的查找方法。

前提

数组为有序数组,数组中无重复元素。

因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件。

二分查找涉及的很多的边界条件,逻辑比较简单,但就是写不好。

  • 到底是 while(left < right) 还是 while(left <= right)?
  • 到底是right = middle呢,还是要right = middle - 1呢?

区间的定义就是不变量。要在二分查找的过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。

写二分法,区间的定义一般为两种,左闭右闭即[left, right],或者左闭右开即[left, right)。

写法

1、左闭右闭

定义 target 是在一个在左闭右闭的区间里,也就是[left, right]

区间的定义这就决定了二分法的代码应该如何写,因为定义target在[left, right]区间,所以有如下两点:

  • while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=
  • if (nums[middle] > target) right 要赋值为 middle - 1,因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle - 1

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
int search(vector<int>& nums, int target) {  // 左闭右闭
int left = 0, right = nums.size() - 1;
while (left <= right) {
int middle = left + ((right - left) >> 1); // 防止溢出
if (nums[middle] > target)
right = middle - 1;
else if (nums[middle] < target)
left = middle + 1;
else
return middle;
}
return -1;
}

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func search(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
middle := left + (right-left)>>1
if nums[middle] > target {
right = middle - 1
} else if nums[middle] < target {
left = middle + 1
} else {
return middle
}
}
return -1
}

2、左闭右开

定义 target 是在一个在左闭右开的区间里,也就是[left, right) ,那么二分法的边界处理方式则截然不同。

有如下两点:

  • while (left < right),这里使用 < ,因为left == right在区间[left, right)是没有意义的
  • if (nums[middle] > target) right 更新为 middle,因为当前nums[middle]不等于target,去左区间继续寻找,而寻找区间是左闭右开区间,所以right更新为middle,即:下一个查询区间不会去比较nums[middle]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size(); // 左闭右开
while (left < right) { // left == right在[left, right)是无效的空间
int middle = left + ((right - left) >> 1);
if (nums[middle] > target) {
right = middle; // target 在左区间,在[left, middle)中
} else if (nums[middle] < target) {
left = middle + 1; // target 在右区间,在[middle + 1, right)中
} else { // nums[middle] == target
return middle; // 数组中找到目标值,直接返回下标
}
}
// 未找到目标值
return -1;
}
作者

SukiEva

发布于

2021-11-21

更新于

2021-12-22

许可协议

CC BY-NC-SA 4.0

评论


取次花丛懒回顾,半缘修道半缘君。

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×