leetcode 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]

分析：由于是在有序数组中查找某个数，故很容易想到首先使用二分查找到该数，因为是有序的，如果这个数存在多个，则肯定是在左边或右边，然后从该位置往左往右遍历，这步操作相当于常数时间复杂度，即整体时间复杂度为O(logN) + O(1)，即符合O(logN)的时间复杂度要求。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = -1;
        int last = -1;
        
        int begin = 0;
        int end = nums.length-1;
        while (begin <= end) {
            int mid = begin + (end-begin)/2;
            if (nums[mid]==target) {
                first = last = mid;
                int left = mid-1;
                int right = mid+1;
                while(left >= 0 && nums[left]==target) {
                    first = left--;
                }
                while(right <= nums.length-1 && nums[right]==target) {
                    last = right++;
                }
                break;
            } else {
                if (nums[mid] > target) {
                    end = mid-1;
                } else {
                    begin = mid+1;
                }
            }
        }
        
        return new int[]{first, last};
    }
}