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

思路：

我的思路：两次二分，找到目标值先别停，向两边移动探测边界。

有些人会这样写，一次二分找到目标值后直接while向两边找，这样的思路会有什么问题呢？这样重复数字越多，我们的算法时间复杂度会越来越接近接近o(n)；

ps：感觉这题做过，而且以前有过更好的思路，现在想不起来了。。。

代码语言：javascript复制

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIndex=findLeft(nums,target);
        //如果没有该target
        if (leftIndex==-1){
            return new int[]{-1,-1};
        }
        int rightIndex=findRight(nums,target);
        return new int[]{leftIndex,rightIndex};
    }

    private int findLeft(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 {
                right=mid-1;
            }
        }
        if (left!=nums.length&&nums[left]==target){
            return left;
        }
        return -1;
    }

    private int findRight(int[] nums, int target) {
        int left= 0,right=nums.length-1;
        while (left<=right){
            int mid=left (right-left)/2;
            if (nums[mid]==target){
                left=mid 1;
            }else if (nums[mid]<target){
                left=mid 1;
            }else {
                right=mid-1;
            }
        }
        // 由于 findFirstPosition 方法可以返回是否找到，这里无需单独再做判断

        return right;
    }


}

击败100%没毛病

ps 算法

0 人点赞