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

1.题目：  

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

步骤一：查找区间左端点

细节图：

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

细节图：

代码： 

代码语言：javascript复制

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.非朴素二分模板：在理解原理基础上

基础 排序 数组 原理 int

0 人点赞