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

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

34. 在排序数组中查找元素的第一个和最后一个位置 - 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。示例 1：输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4] 示例 2：输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1] 示例 3：输入：nums = [], target = 0 输出：[-1,-1] 提示： * 0 <= nums.length <= 105 * -109 <= nums[i] <= 109 * nums 是一个非递减数组 * -109 <= target <= 109

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

解法：

解题思路

看代码，nums 有序，先二分找 target，如果找到 target 则向前找是否还有 target，这个过程中不断更新 start 指针，end 则是相反的向后查找

算法流程

代码


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

        int l = 0, r = nums.length - 1;
        int start = -1, end = -1;

        while(l <= r) {
            int mid = ((r-l)>>1)+l;
            if(nums[mid] == target) {
                start = mid;
                r = mid - 1;
            }
            else if(nums[mid] > target) r = mid - 1;
            else l = mid + 1;
        }

        l = 0;
        r = nums.length - 1;
        while(l <= r) {
            int mid = ((r-l)>>1)+l;
            if(nums[mid] == target) {
                end = mid;
                l = mid + 1;
            }
            else if(nums[mid] > target) r = mid - 1;
            else l = mid + 1;
        }

        return new int[]{start, end};
    }
}

细节

第二次记得重新初始化边界


l = 0;
r = nums.length - 1;

如果为空数组则直接返回


if(nums.length == 0) return new int[]{-1, -1};

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

解法：

相似题