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

题目

给你一个按照非递减顺序排列的整数数组 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

我的解答

思路：时间复杂度要求O(log n)，使用折半查找。找到位置即可，随后两边扩散找到第一和最后一个位置。

public class FindFirstAndLastPositionOfElementInSortedArray {

    public int[] searchRange(int[] nums, int target) {

        int []ret = new int[]{-1,-1};
        if(nums.length == 0 ){
            return ret;
        }
        int len = nums.length;
        // 1.折半法找到Pos
        int pos = searchOnePos(nums,target,0,len-1);
        if(pos == -1){
            return ret;
        }
        // 2.两边扩散
        ret[0] = searchFirst(nums,target,pos,-1);
        ret[1] = searchFirst(nums,target,pos,1);
        return ret;
    }

    private int searchFirst(int[] nums, int target,int pos, int step){

        while(pos>=0 && pos<nums.length && nums[pos] == target){
            pos = pos + step;
        }
        return pos-step;
    }

    private int searchOnePos(int[] nums, int target,int left, int right){

        if(left >= right){
            if(nums[left] == target){
                return left;
            }
            return -1;
        }
        if(left + 1 == right){
            if(nums[left] == target){
                return left;
            }else if(nums[right] == target){
                return right;
            }
            return -1;
        }

        int mid = (right-left)/2 + left;
        if(nums[mid] == target){
            return mid;
        }

        if (nums[mid] > target) {
            return searchOnePos(nums,target,left,mid-1);
        } else  {
            //(nums[mid] < target)
            return searchOnePos(nums,target,mid+1,right);
        }
    }

    @Test
    public void test(){

        int []nums = new int[] {0,1,2,3,4,5,5,6,7,7,8,8,9,9};
        int target = 0;
        int [] expected = new int[]{0,0};
        Assert.assertArrayEquals(expected,searchRange(nums,target));
    }

}

官方参考

class Solution {
    
    public int GetRightBorder(int[] nums, int target){
        int rightborder = -2;

        int left = 0;
        int right = nums.length - 1;

        while(left <= right){
            int middle = left + (right - left) / 2;
            if(nums[middle] <= target){
                left = middle + 1;
                rightborder = left;
            }
            if(nums[middle] > target){
                right = middle - 1;
            }
        }
        return rightborder;
    }

    public int GetLeftBorder(int[] nums, int target){
        int leftborder = -2;

        int left = 0;
        int right = nums.length - 1;

        while(left <= right){
            int middle = left + (right - left) / 2;
            if(nums[middle] < target){
                left = middle + 1;
            }
            if(nums[middle] >= target){
                right = middle - 1;
                leftborder = right;
            }
        }
        return leftborder;
    }    
    
    public int[] searchRange(int[] nums, int target) {
        int leftborder = GetLeftBorder(nums, target);
        int rightborder = GetRightBorder(nums, target);

        if(leftborder == -2 || rightborder == -2){
            return new int[]{-1,-1};
        }
        if(rightborder - leftborder > 1){
            return new int[]{leftborder + 1, rightborder - 1};
        }
        else{
            return new int[]{-1,-1};
        }
    }
}

分别找到左右两边的边界（第一个不等于的位置），两边边界分别+/- 得到。