经过多年教授算法后,我解决二分查找问题的方法是将起始点和结束点设置在元素上而不是在数组外部。这样我可以感受到发生了什么,一切都在掌控之中,而不会对解决方案感到神秘。
解决二分查找问题(以及许多其他基于循环的解决方案)的关键点是良好的不变量集合。选择正确的不变量使得问题解决不费吹灰之力。虽然我很早就在大学里学习了不变量的概念,但花了我很多年才理解它。
即使您想通过在数组外部选择起始或结束点来解决二分查找问题,只要有适当的不变量也可以实现。话虽如此,我的选择如上所述,总是将起始点放在数组的第一个元素上,将结束点放在最后一个元素上。
因此,总结一下,我们迄今为止所拥有的内容如下:
int start = 0;
int end = a.length - 1;
现在讲不变量。我们当前拥有的数组是[start,end]。我们还不知道元素的任何信息。它们中的所有元素都可能大于目标值,也可能都小于目标值,或者有些小于目标值而有些大于目标值。因此,到目前为止,我们不能对这些元素做出任何假设。我们的目标是找到第一个大于目标值的元素。因此,我们选择以下不变量:
右侧所有元素均大于目标值。
左侧所有元素小于或等于目标值。
我们很容易看出,在开始时(即进入任何循环之前),我们的不变量是正确的。所有在开始左侧的元素(基本上没有元素)都小于或等于目标值,对于结束位置同理。
有了这个不变量,当循环完成时,结束位置后面的第一个元素将是答案(记住不变量,即结束位置右侧的所有元素都大于目标值?)。因此,answer = end + 1
。
此外,我们需要注意,当循环完成时,开始位置将比结束位置多一。也就是说,start = end + 1
。因此,我们可以同样地说,开始位置也是答案(不变量是左侧所有元素小于或等于目标值,因此开始位置本身就是第一个大于目标值的元素)。
综上所述,以下是代码。
public static int find(int a[], int target) {
int st = 0;
int end = a.length - 1;
while(st <= end) {
int mid = (st + end) / 2;
if (a[mid] <= target) {
st = mid + 1;
} else {
end = mid - 1;
}
}
return st;
}
关于解决二分查找问题的这种方式,有一些额外的注意事项:
这种解决方案总是至少将子数组的大小缩小
1
。这在代码中很明显。新的开始或结束位置要么是
+1
,要么是
-1
在中间位置。我喜欢这种方法比在两边或一边包括中间位置然后再推理为什么算法正确。这样更具体,更不容易出错。
while 循环的条件是
st <= end
,而不是
st < end
。这意味着进入 while 循环的最小尺寸是大小为
1
的数组。这完全符合我们的预期。在其他解决二分查找问题的方法中,有时最小尺寸是大小为
2
的数组(如果
st < end
),老实说,我发现始终考虑包括大小为 1 的所有数组尺寸要容易得多。
因此,希望这可以澄清这个问题以及许多其他二分查找问题的解决方案。把这个解决方案当作一种专业的方式来理解和解决更多的二分查找问题,而不会摇摆不定算法是否适用于边缘情况。