“看到有序数组，首先想到二分”

或数组存在两段性（如对某条件：左边一段都为true,右边一段都false）lc.278

关键在于找到两段性，有些比较隐蔽，如lc.287

戳！！~

问题分类

• 找出目标值
• 找出满足条件的左界
• 找出满足条件的右界

找出目标值

	private int binarySearchWithoutR(int[] nums, int target) {
        int left = 0;
        int right = nums.length -1; 

        while(left < right) { // 注意
            int mid = left + (right - left) / 2 ;
            if(nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1; 
        }
        return -1;
    }

注意： 有些问题不是简单的等于target，如找最小值(lc.157)、找单个出现的元素(lc.540)等，可以转成满足条件的左界/右界问题（满足条件的只有一个元素）

找出满足条件的左界

public class Solution extends VersionControl {//满足条件的最左边界
    public int firstBadVersion(int n) {
        int l=1;
        int r=n;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(isBadVersion(mid)){//如果mid值满足某条件，先不慌返回它，而是继续向它的左边找满足条件的
                r=mid-1;
                //收缩右边界，可以-1的原因是，即使只有当前mid一个数满足条件，它左边的都不满足，
                //那么l一次次收缩后，因为while(l<=r)，最后一次循环，l=r,不满足条件，则l+1，还是可以回到当前mid，最后返回l即可
            }
            else{
                l=mid+1;
            }
        }
        return l;
    }
}

找出满足条件的右界

 public int mySqrt(int x) {
        int l=0;
        int r=x;
        int ans=-1;
        while(l<=r){
            int mid=l+(r-l)/2;
            if((long)mid*mid<=x){
                //ans=mid;//满足条件就记录下来，但还不是最右的，所以动左界，缩小范围
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }
        return r;
    }

特殊情况

有时候只能while(l<r),如r初始值取得是nums.length时，或lc.540，那么往往右边界收缩也要调整为r=mid，而不再-1