关于二分查找
二分查找或许是很多人学习的第一个算法,其简洁明快,但是在实际应用中,你却会看到许多种写法的二分查找,而这些写法,仅是细节处的区别。
这些不同写法的二分查找,究竟哪一个才是正确的?还是,无论怎么写,达到目的便可以称之为二分查找?
常规写法一
1 | public static int bSearch(int[] arr, int start, int end, int key){ |
这种写法便是我所学习的,或许也是大多数人所学习的,如果存在,其查找过程如下:
![二分_1.png](/img/loading.gif)
如果目标不存在,则查找过程如下所示:
![二分_2.png](/img/loading.gif)
如上种写法,注意,在参数传入的时候,数组的两边都是封闭的,也就是说,在传入数组的时候,需要传入 length-1
,使得 end =length-1
。
常规写法二
但是,好多人可能还见到过另一种写法:
1 | public static int bSearch(int[] arr, int start, int end, int key){ |
注意此种写法与上种写法的差异:
start <= end
变为start < end
end = mid - 1
变为end = mid
经过以上改动,其传参之时,便是一个左闭右开的区间了,如需传入整个数组,则直接传入 length
即可,
那么为何如此?
一与二的差异
第一种与第二种写法,实质上是相同的,而所产生了写法上差异的原因,本质在于区间范围的不同。
和所有算法一般,代码希望不重复,不遗漏地解决问题,故产生了两种不同的细节。
写法一的细节
正如我在写法一最后所说,写法一的左右区间都是封闭的。
end = mid - 1
- 在搜索判断的时候,只要
arr[mid] > key
的时候,我们接下来要做的便只是缩短区间,将区间缩为[start, mid-1]
- 由于此区间便是左右封闭的,那么直接写为
end = mid - 1
即可。
- 在搜索判断的时候,只要
start <= end
- 为何这么写?答为:为了方便。
- 如果写为
start < end
,那么,代码有可能在start == end
的时候终止,而key
有可能恰好就在start
处,这时候,返回-1
显然是不合适的。 - 写为
start < end
可不可以?- 可以,当然,你需要在跳出循环之后进一步判断,当然,此时不能单纯地使用
arr[start]
,可能会超出数组索引,比较麻烦。
- 可以,当然,你需要在跳出循环之后进一步判断,当然,此时不能单纯地使用
写法二的细节
第二种写法一开始便认为区间是左闭右开的。
end = mid - 1
- 同样地,
arr[mid] > key
之时,也需要缩短区间至[start, mid-1]
- 由于第二种写法是左闭右开的,也就是说要将区间缩为
[start, mid)
,故需要写为end = mid
- 同样地,
start < end
- 为何这么写?答为:为了不陷入死循环。
- 和上面为了方便不同,此处如果写为
<=
便会直接出错- 如果写为
<=
如果此时刚好mid == start == end
并且arr[mid] > key
,便一直会执行end == mid
,从而导致start === end
,从而造成死循环! - 第一种写法则不同,其是
end = mid - 1
,可以直接跳过。
- 如果写为
查找左侧边界
当数组有重复元素时,比如:[1, 2, 2, 2, 2, 3, 4, 5]
,此时若需要寻找一个元素,我们更希望寻找到一个边界的元素,比如寻找 2
,我们更希望寻找到最左边的 2
或者是最右边的 2
。
寻找左侧边界,便是这种寻找最左边元素的二分算法。
首先贴出代码让大家感受一番:
1 | public static int lowerBound(int[] arr, int start, int end, int key){ |
有了上面对于细节的描述,我想,现在便可以很容易地看出:
- 上边的代码会停在最左边的元素上(如果有这个元素的话)。
- 上边的代码会停在小于查找的元素中最大的那个上(如果没有这个元素的话)
查找右侧边界
代码如下:
1 | public static int upperBound(int[] arr, int start, int end, int key){ |
同样,可以看出:
- 上述代码如果直接返回,那么查找的便是大于查找元素中最小的元素,即便数组中有所要查找的元素。
- 如果需要严格地查找右边界,那么可以返回
start-1
附录
其实上面所说的,所写的都可以作为一个模板来使用,通过更改终止条件等方式达到自己想要的目的!
比如,leetcode
上一些打着二分搜索的题目!