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

一、题目

给定一个按照升序排列的整数数组 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]

二、解答

2.1 方法一：二分查找

public int[] searchRange(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;

        int index = -1;
        //利用二分查找寻找元素
        while (l <= r){
            int mid = (l+r)/2;
            if (target == nums[mid]){
                index = mid;
                break;
            }else if (target >nums[mid]){
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }

        int start = index;
        int end = index;
        if (index == -1){
            return new int[]{start,end};
        }

        //更新start
        while (start > 0){
            start--;
            if(nums[start] != target){
                start++;
                break;
            }
        }

        //更新end
        while (end < nums.length - 1){
            end++;
            if(nums[end] != target){
                end--;
                break;
            }
        }

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