参考自B站灵茶山艾府

红蓝染色法

我们用left代表蓝色, right代表红色, 蓝色和红色一定是互斥的, 比如蓝色规定代表<= target的区域, 那么红色就代表>target的区域

我们如何才能表示成红蓝染色呢？我们可以采用"(" / "[" left, right "]" / ")"的形式。我们规定"["表示元素本身以及区域以内的元素是未染色的，规定"("则不包含元素本身。括号内的是还未染色的区域，括号外的是已经染色的区域，这样我们就可以形象地表示出红色区域，蓝色区域以及未处理的元素区域。

我们通过不断将数组的中间元素和要寻找的元素相比较，来染色未处理得区域，直到所有区域都染色完毕。

值得一提的是，left和right的移动应该根据它们代表的是开区间还是闭区间来移动。如果是闭区间的话，left或right不能指向mid本身，因为闭区间表示元素本身以及区域内的元素是未处理的，但是很明显，mid已经处理了。

由于数组每次都收缩一半，最终的时间复杂度是O(logn)的。

模板

这里就根据灵神推荐的开区间写法来写。

查找指定元素

class Solution {
    public int search(int[] nums, int target) {
        int ans = lowerBound(nums, target);
        return ans < nums.length && nums[ans] == target ? ans : -1;
    }

    private int lowerBound(int[] nums, int target) {
        int left = -1;
        int right = nums.length;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return right;
    }
}

查找最后一个</<= 或者第一个>/>=

class Solution {
    public int search(int[] nums, int target) {
        int ans = lowerBound(nums, target);
        return ans < nums.length && nums[ans] == target ? ans : -1;
    }

    private int lowerBound(int[] nums, int target) {
        int left = -1;
        int right = nums.length;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left/right;
    }
}

边界条件是