循环不变式（Loop Invariant）

    什么叫循环不变式？不只是一种计算机科学的思想，准确地说是一种数学思想。在数学上阐述了通过循环（迭代、递归）去计算一个累计的目标值的正确性，属于基础数学的范畴，而且在计算机上也应用广泛。

    循环不变式主要用来帮助理解算法的正确性，其主体是不变式，也就是一种描述规则的表达式。过程分三个部分：初始，保持，终止。　
　　（1）初始：保证在初始的时候不变式为真。
　　（2）保持：保证在每次循环开始和结束的时候不变式都为真。
　　（3）终止：如果程序可以在某种条件下终止，那么在终止的时候，就可以得到自己想要的正确结果。
举个栗子：

    public static int binarySerach1(int[] arr, int target) {
        //循环不定式条件：定义一个区间[left...right]，在这个区间内查找target
        int left = 0, right = arr.length - 1;
        int mid = -1;
        while(left <= right){//[left...right]满足条件，比如[12, 12]数组中有一个元素12
            mid = left + ((right-left)>>1);//注意符号优先级
            if(arr[mid] == target){
                return mid;
            }
            if(arr[mid] < target){//更新左边界，不包含mid，维持循环不定式：[mid + 1...right]成立
                left = mid + 1;
            }else{//更新右边界，不包含mid，维持循环不定式：[left...mid - 1]成立
                right = mid - 1;
            }
        }
        return mid;
    }

    public static int binarySerach2(int[] arr, int target) {
        //循环不定式条件：定义一个区间[left...right)，在这个区间内查找target
        int left = 0, right = arr.length;
        int mid = -1;
        while(left < right){//[left...right)满足条件
            mid = left + ((right-left)>>1);//注意符号优先级
            if(arr[mid] == target){
                return mid;
            }
            if(arr[mid] < target){//更新左边界，不包含mid，维持循环不定式：[mid + 1...right)成立
                left = mid + 1;
            }else{//更新右边界，不包含mid，维持循环不定式：[left...mid)成立
                right = mid;
            }
        }
        return mid;
    }

参考：
1.https://baike.baidu.com/item/%E5%BE%AA%E7%8E%AF%E4%B8%8D%E5%8F%98%E5%BC%8F/10593291?fr=aladdin
2.慕课网：玩转算法面试 作者：liuyubobobo