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

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值,返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

1.实现方式一:使用线性查询 ,先找到第一个数据是target的,然后从当前元素开始,一直找找到一个不相同的元素,停止循环,然后结束索引就是这个不相同数据的的前一位。

2.二分查询法:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function extremeInsertionIndex(nums,target,left){
    let lo = 0;
    let hi = nums.length;//对于查询左测数据的时候length或是length-1都没有关系,但是在查询右侧的时候,如果最后一个数是target,就要像向下再找一个不是target的数据,所以要将left+1
    while(lo<hi){
       let  mid = parseInt((lo+hi)/2);
        if(nums[mid]>target||(left&& target == nums[mid])){
            hi = mid;
        }els
            lo= mid+1;
        }
    }
    return lo;
}

var searchRange = function(nums, target) {
     let temp = [-1,-1]
    //获取最左边的下标
    let leftIndex = extremeInsertionIndex(nums,target,true)
    if(leftIndex ==nums.length||nums[leftIndex]!=target){
        return temp;
    }
    temp[0] = leftIndex;
    temp[1]=extremeInsertionIndex(nums,target,false)-1;
    return temp;
    
};

实现:主要是利用二分查询的方式:
   查询最左侧的元素时:最主要的目的是获取最小的target索引

   如果在查询最左侧的元素的时候,找不到target元素,就说明不存在该元素,直接结束程序

   查询最右侧的元素时:最主要的是查询不是target元素的索引

 

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

你可能感兴趣的