二分查找

在二分查找的过程中，必须保持不变量，也就是循环不变量

循环不变量的定义：在循环过程中报错不变的性质

主要作用：

  • 让算法设计的逻辑更加清晰
  • 让代码更加简洁，有更强的逻辑性
  • 证明算法的正确性

比如

  • 在选择排序算法中，我们可以写出循环不变的性质：区间nums[0…i]里保存了数组力最小的i个元素，并且nums中的元素按升序排列。无论是在循环的初始化、循环的过程中、循环的结束，这个循环不变性质都是恒定不变的。我们可以根据这个不变性质去设计算法，去让程序更有逻辑性

  • 对二分法进行代码实现的时候，我们可以定义其循环不变的性质：循环过程中其区间是左闭右开的。我们在写代码的时候，依据这个不变性质，就不会造成区间一会是左闭右开，一会是左闭右闭，造成代码错误