二分查找的循环条件及指针终止位置问题
二分查找的循环条件及指针终止位置问题
常见的二分搜索法的循环迭代方法分为：左闭右开 和 左闭右闭 两种方式
-
左闭右开：由于右边界开放，例如[1,1)是矛盾的，因此循环条件为
while(l<r)。闭合指后续迭代仍需要进行对其元素进行比较。因此每次迭代结束，左指针l移动到中点的下一位l = mid+1，而不需要移动到中点位置，因为中点位置已被和目标值比较过；开放意味着后续不需要再进行比较，因此每次右指针r需要移动到已经比较过的中点位置mid； -
左闭右闭：由于右边界闭合，例如[1,1]是合理的，因此循环条件为
while(l<=r)；由于左右边界都闭合，这意味着后续迭代需要对左右边界即l和r指向的元素进行判断。因此每次迭代结束，左指针l移动到中点的下一位l = mid+1，右指针r移动到中点的前一个位置r = mid-1，因为mid位置已经被比较过了。
详细解释为什么
while(l<r)时需要右指针r移动到mid，而while(l<=r)时需要右指针r移动到mid-1：首先，这两种情况下，每次循环的不变量都是左指针要移动到mid的下一位（左闭）。
-
当
while(l<r)时，我们考虑l+1=r这种情况，即l指针位于r指针的前一位，此时mid指向l：（1）若目标值target < nums[mid]=nums[l]，此时r指针移动到mid也就是l的位置，l=r正常结束。（2）若目标值target > nums[mid]=nums[l]，l指针移动到mid的下一位r的位置，此时l=r循环结束，但r指向的元素未被判断。这就要求我们在先前已经对右指针r指向的元素进行过判断，结束才是合理的。因此，因此当移动右指针时，我们必须保证右指针指向的元素是在先前已经被判断过的，所以每次右指针要移动到mid的位置，若移动到mid-1,那么r指针指向的位置就没有被判断，在上述情况下，就是错误的结束。同时这就是 右开 的由来，每次循环不用判断r指向的元素，因为它在上次移动到的是已经比较过的元素的位置。 -
当
while(l<=r)，同样考虑l+1=r这种情况：（1）情况同上相同。（2）当目标值target > nums[mid]=nums[l]时，l指针移动到mid的下一位r的位置，l=r仍未结束，此时mid=l=r对r进行判断。这意味着右指针r指向的元素在后续会被判断到，这就要求，我们每次迭代改变右指针r的位置时，是先前未被判断过的即可，即每次r指针移动到mid-1的位置。这是 右闭 的由来，因为右边界r的指向未被比较过，需要在后续比较。
mid = ( l + r ) / 2下，指针终止情况
针对以上两种循环迭代方法，本文枚举了所有指针终止位置的情况。其中包括不引入辅助元素、引入左边界辅助元素、引入右边界辅助元素以及同时引入左右边界辅助元素时，左右指针的终止位置情况。旨在将规律具象化，便于理解。（注：在不越界的情况下，令 mid = ( l + r ) / 2）
不引入辅助元素
引入左边界
引入右边界
引入左右边界
总结
左闭右开：
- 在不引入辅助边界的情况下，除了大于右边界的目标值，左右指针
l和r共同指向第一个大于目标的数 - 当引入了右辅助边界时，左右指针
l和r共同指向第一个大于目标的数。
左闭右闭：
- 无论是否引入左右辅助边界，右指针
r始终指向小于目标的最近位置的数，左指针l始终指向大于目标的最近位置的数
mid = ( l + r + 1) / 2下，指针终止情况
