Java在排序数组中查找元素的第一个和最后一个位置(二分法)

34. 在排序数组中查找元素的第一个和最后一个位置

解题思路:

二分法:

• 数组单调有序
• 时间复杂度O(nlogn)

满足上述条件就可以先考虑二分法

使用两个二分查找, 一个二分查找左边界, 一个二分查找右边界
查找左边界时:
当nums[mid] = target时, right = mid - 1;
查找右边界时:
当nums[mid] = target时, left = mid - 1;

1. 为何查找左边界时, 当nums[left] == target直接返回left?
   处于while循环中的时候, 由于一直在二分查找, 所以一定会有指针left和指针right指向同一个元素下标的时候
   此时, left = right = mid、nums[left] = nums[right] = nums[mid] = target, 继续执行条件3right = mid - 1;, 则right在left左侧, 跳出while循环
   跳出while循环后, left就是左边界, 同时 nums[left] = target
2. 同理, 查找右边界时, 当nums[right] == target直接返回right

class Solution {
    public int leftNum(int[] nums, int target){
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{//条件3
                right = mid - 1;
            }
        }
        if(nums[left] == target){
            return left;
        }else{
            return -1;
        }
    }

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

    public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0 || target < nums[0] || target > nums[nums.length - 1]){
            return new int[]{-1, -1};
        }
        int ln = leftNum(nums, target);
        int rn = rightNum(nums, target);
        return new int[]{ln, rn};
    }
}