<Binary Search> 81 （高频）34 (很难hard, 高频)315 （hard）354

81. Search in Rotated Sorted Array II

如果中间的数小于最右边的数，则右半段是有序的，若中间数大于最右边数，则左半段是有序的。而如果可以有重复值，就会出现来面两种情况，[3 1 1] 和 [1 1 3 1]，对于这两种情况中间值等于最右值时，目标值3既可以在左边又可以在右边，那怎么办么，对于这种情况其实处理非常简单，只要把最右值向左一位即可继续循环，如果还相同则继续移，直到移到不同值为止

class Solution {
    public boolean search(int[] nums, int target) {
        int n = nums.length, left = 0, right = n - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) return true;
            if(nums[mid] < nums[right]){
                if(nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }else if(nums[mid] > nums[right]){
                if(nums[left] <= target && target < nums[mid]) right = mid - 1;
                else left = mid + 1;
            }else --right;
        }
        return false;
    }
}

 34. Find First and Last Position of Element in Sorted Array（高）

上面的算法不是严格意义上的 O(logn) 的算法，因为在最坏的情况下会变成 O(n)，比如当数组里的数全是目标值的话，从中间向两边找边界就会一直遍历完整个数组，那么下面来看一种真正意义上的 O(logn) 的算法，使用两次二分查找法，第一次找到左边界，第二次调用找到右边界即可

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        res[0] = -1;
        res[1] = -1;
        if(nums == null || nums.length == 0) return res;
        res[0] = findFirst(nums, target);
        res[1] = findLast(nums,target);
        return res;
    }
    
    private int findFirst(int[] nums, int target){
        int start = 0, end = nums.length - 1;
        while(start + 1 < end){
            int mid = start + (end - start) / 2;
            if(nums[mid] >= target){// 往左边找
                end = mid;
            }else{
                start = mid;
            }
        }
        if(nums[start] == target) return start;
        else if(nums[end] == target) return end;
        return -1;
    }
    
    private int findLast(int[] nums, int target){
        int start = 0, end = nums.length - 1;
        while(start + 1 < end){
            int mid = start + (end - start) / 2;
            if(nums[mid] <= target){//往右边找
                start = mid;
            }else{
                end = mid;
            }
        }
        if(nums[end] == target) return end;
        else if(nums[start] == target) return start;
        return -1;
    }
}

354. Russian Doll Envelopes

以width升序， 当width相同时采用降序。

信封的宽度还是从小到大排，但是宽度相等时，我们让高度大的在前面。那么现在问题就简化了成了找高度数字中的LIS，完全就和之前那道Longest Increasing Subsequence一样了

t

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if(envelopes.length < 2) return envelopes.length;
        
        Arrays.sort(envelopes, new EnvelopeComparator());
        int[] dp = new int[envelopes.length];
        int size = 0;
        
        for(int[] envelope : envelopes){
            int left = 0, right = size, mid = 0;
            while(left < right){
                mid = left + (right - left) / 2;
                if(dp[mid] < envelope[1]) left = mid + 1;
                else right = mid;
            }
            
            dp[left] = envelope[1];
            if(left == size) size++;
        }
        return size;
    }
    
    class EnvelopeComparator implements Comparator<int[]>{
        public int compare(int[] e1, int[] e2){
            return e1[0] == e2[0] ? e2[1] - e1[1] : e1[0] - e2[0];
        }
    }
}

315. Count of Smaller Numbers After Self

BST: 时间复杂度O(nlongn) ~O(n^2 )，当BST不平衡时时间复杂度O(n ^2)。用merge sort能够稳定在O(nlongn)，但较难理解。

把数组从后往前添加到BST中，

　　1. val == root.val, root.count++，表示这个节点的值相同的个数+1

　　2. val < root.val，说明这个数值更小，添加到左子树内.

　　

,

class Solution {
    class Node{
        int val, count, left_count;
        Node left, right;
        public Node(int val){
            this.val = val;
            this.count = 1;
        }
        public int less_or_equal(){
            return count + left_count;
        }
    }
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        if(nums.length == 0) return ans;
        int n = nums.length;
        Node root = new Node(nums[n - 1]);
        ans.add(0);
        for(int i = n - 2; i >= 0; i--){
            ans.add(insert(root, nums[i]));    
        }
        Collections.reverse(ans);
        return ans;
    }
    
    private int insert(Node root, int val){
        if(root.val == val){
            ++root.count;
            return root.left_count;
        }else if(val < root.val){
            ++root.left_count;
            if(root.left == null){
                root.left = new Node(val);
                return 0;
            }
            return insert(root.left, val);
        }else{
            if(root.right == null){
                root.right = new Node(val);
                return root.less_or_equal();
            }
            return root.less_or_equal() + insert(root.right, val);
        }
    }
}