PEANUT996

二分查找开闭区间与循环不变量

二分查找关键是找循环不变量

二分查找的三种写法

闭区间

循环结束后， 指针所处位置

循环不变量

nums[left - 1] 满足 condition

nums[right + 1] 满足 !condition

这里的condition - n ≤ 4

代码


        int left = 0, right = nums.length - 1;

        while(left <= right) { // 合法区间
            int mid = left + (right - left)/2;
            if(condition) {
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }
        }
        return left - 1 ; //或者right + 1;

开区间

循环结束后指针所处位置

循环不变量

nums[left] 满足 condition

nums[right] 满足 !condition

这里的condition - n ≤ 4

代码


        int left = -1, right = nums.length;

        while(left + 1 != right) { // 合法区间
            int mid = left + (right - left)/2;
            if(condition) {
                left = mid;
            }else if(nums[mid] > target){
                right = mid;
            }
        }
        return left; //或者right;

左闭右开区间

循环结束后left == right

循环不变量

nums[left - 1] 满足 condition

nums[right] 满足 !condition

这里的condition - n ≤ 4

代码


        int left = 0, right = nums.length;

        while(left < right) { // 合法条件
            int mid = left + (right - left)/2;
            if(condition) {
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid;
            }
        }
        return left  ; //或者right ;