二分查找的循环条件及指针终止位置问题

二分查找的循环条件及指针终止位置问题

常见的二分搜索法的循环迭代方法分为:左闭右开左闭右闭 两种方式

  • 左闭右开:由于右边界开放,例如[1,1)是矛盾的,因此循环条件为while(l<r)。闭合指后续迭代仍需要进行对其元素进行比较。因此每次迭代结束,左指针l移动到中点的下一位l = mid+1,而不需要移动到中点位置,因为中点位置已被和目标值比较过;开放意味着后续不需要再进行比较,因此每次右指针r需要移动到已经比较过的中点位置mid

  • 左闭右闭:由于右边界闭合,例如[1,1]是合理的,因此循环条件为 while(l<=r);由于左右边界都闭合,这意味着后续迭代需要对左右边界即lr指向的元素进行判断。因此每次迭代结束,左指针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)

不引入辅助元素

引入左边界

引入右边界

引入左右边界

总结

左闭右开:

  • 在不引入辅助边界的情况下,除了大于右边界的目标值,左右指针lr共同指向第一个大于目标的数
  • 当引入了右辅助边界时,左右指针lr共同指向第一个大于目标的数。

左闭右闭:

  • 无论是否引入左右辅助边界,右指针r始终指向小于目标的最近位置的数,左指针l始终指向大于目标的最近位置的数


mid = ( l + r + 1) / 2下,指针终止情况

热门相关:九龙神鼎   第99次离婚   隋唐君子演义   我真不是学神   脑洞大爆炸