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

两个二分查找分别寻找

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

        /**
         * 分别寻找第一个和最后一个target
         */
        int left = 0;
        int right = nums.length - 1;
        int start = -1;

        while (left <= right){

            int mid = left + (right - left) / 2;

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

                /**
                 * 如果找到了一个target，先保存位置，然后继续向左寻找
                 */
                start = mid;
                right = mid - 1;
            }
        }

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

        while (left <= right){

            int mid = left + (right - left) / 2;

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

                /**
                 * 如果找到了一个target，先保存位置，然后继续向右寻找
                 */
                end = mid;
                left = mid + 1;
            }
        }

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

/**
 * 时间复杂度 O(logn)
 * 空间复杂度 O(1)
 */

一个二分查找

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

        /**
         * 先找到任意一个target，记录位置
         */
        int left = 0;
        int right = nums.length - 1;
        int start = -1;
        int end = -1;

        while (left <= right){

            int mid = left + (right - left) / 2;

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

                start = mid;
                end = mid;
                break;
            }
        }

        /**
         * 然后双指针向左向右遍历，找到第一个和最后一个位置
         */
        while (start - 1 >= 0 && nums[start - 1] == target){
            start--;
        }

        while (end >= 0 && end + 1 < nums.length && nums[end + 1] == target){
            end++;
        }

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

/**
 * 时间复杂度 O(logn)
 * 空间复杂度 O(1)
 */

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