二分查找一＞:在排序数组中查找元素的第一个和最后一个位置

用户11305962

发布于 2024-10-09 15:59:29

930

发布于 2024-10-09 15:59:29

文章被收录于专栏：学习

1.题目：

2.解析:这里不能用传统二分，因为涉及范围，传统二分时间复杂度会降为O(N)，要做些改动。

步骤一：查找区间左端点

细节图：

步骤二：查找区间右端点：

细节图：

代码：

public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;
        if(nums.length == 0) return ret;

        //二分查找区间左端点
        int left = 0;
        int right = nums.length-1;
        while(left < right){
            int mid = left+(right-left)/2;
            if(nums[mid] < target) left = mid+1;
            else right = mid;
        }

        //判断是否有结果
        if(nums[left] == target){
            ret[0] = left;
        }else {
            return ret;
        }

        //二分查找区间右端点
        left = 0;
        right = nums.length-1;
        while(left < right){
            int mid = left+(right-left+1)/2;
            if(nums[mid] <= target) left = mid;
            else right = mid-1;
        }

        //判断是否有结果
        ret[1] = left;
        return ret;
    }

3.非朴素二分模板：在理解原理基础上