二分法变形

1. 原二分法针对需求是：在有序的数组中查找元素k
   题：比如升序数组nums={1,2,3,5,8,9}中 查询是否有k=3
   时间 O(logn)

    int search(int[] nums, int key) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid =left+(right - left)/2; //   int mid =left+((right - left)>>1)
            if (nums[mid] == key) {
                return mid;
            } else if (nums[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

2. 变形：在有序但有重复元素的数组中查找元素k的第一个出现index
   题：比如升序数组nums={1,2,3,3,8,9}中 查询是否有k=3
   利用两个指针来找出第一个命中index，利用循环找出边界

   int search(int[] nums, int key) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == key) {
                right = mid;
            } else if (nums[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if(nums[left] == key){
            return left;
        }
        return -1;
    }