谈谈循环不变量

December 15, 2021 2919

循环不变量（loop invariant）

在使用循环的算法里，可以通过循环不变量证明其正确性。

所谓循环不变量是指一种在整个循环过程中保持不变的性质，它必须在以下3种情况下均保持不变，且该性质在循环终止后能证明算法的正确性。

  1. 初始化（循环初始化后，循环条件测试前）
  2. 迭代（第 n 次迭代后，第 n+1 次迭代前）
  3. 结束（循环终止即循环条件判断为 false 时）

二分法理解循环不变量

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4

示例 4:
输入: nums = [1,3,5,6], target = 0
输出: 0

示例 5:
输入: nums = [1], target = 0
输出: 0

提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104

Related Topics
数组
二分查找

我自己的理解：使用二分法一直盯着right，保持循环不变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int searchInsert(int[] nums, int target) {
      	//定义target在左闭右闭合的区间范围里。
        int left = 0;
        int right = nums.length - 1;
        //由于target在一个闭合区间里，那么left=right的时候式子也成立，当left>right的时候式子不成立，则可以推出，while()循环条件是
        //left<=right（取补集）。注意这里很容易错，一定要注意推到。
        //就是循环不变式满足：如果在循环的每一步，这个式子都是正确的，那么循环结束后，这个式子也正确。
        //此问题中初始化时定义区间为[0,nums.length - 1],那么根据循环不变量原理则在循环的整个过程中这种模式是不变的
        //都是闭区间的模式。我们可以根据此检验代码的正确性。
        //因为left，right是闭合区间，所以left和right是可以取到的
        while(left <= right){
            int middle = left + (right - left) / 2;
            if(target >nums[middle] ){
                //如果要找的数比中间值大，说明在区间右边。根据循环不变式，那么当改变left指针的时候，其也是左边闭合的
                //此时left的值应该能被取到，因此left=middle+1
                left=middle+1;
            }
            if(target < nums[middle] ){
                right=middle-1;//同理，right的值也能被取到
            }
            if(target == nums[middle] ){
                return  middle;
            }
        }
        return  right+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length;//注意此处定义的右边为数组的长度，因此其右端点的值是取不到的
        //也就是左闭右开区间[left,right)，因此left!=right，当left大于等于right的时候循环结束
        //循环中的条件为left<right
        while(left <right){
            int middle = left + ((right - left) >> 1);
            if(target >nums[middle] ){
                //如果要找的数比中间值大，说明在区间右边。根据循环不变式，那么当改变left指针的时候，其也是左边闭合的
                //此时left的值应该能被取到，因此left=middle+1
                left=middle+1;
            }
            if(target < nums[middle] ){
                //当要找的值比中间值小的时候，说明区间在左边，由于是左闭右开的区间，所以右端点
                //不能被取到，如果当right=middle-1时候，值是有可能取到的，当right=middle时候
                //由于要找的值是比middle小的，所以是不能被取到的，根据循环不变量原理区间是[0,right)
                //right为middle时候取不到
                right=middle;
            }
            if(target == nums[middle] ){
                return  middle;
            }
        }
        //注意此时返回的是right
        return  right;
    }
}
查看评论