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]

解法一：
遍历数组

 1 class Solution {
 2     public int[] searchRange(int[] nums, int target) {
 3         int[] res = {-1,-1};
 4         for(int i=0;i<nums.length;i++) {
 5             if(nums[i]==target) {
 6                 res[0] = i;
 7                 break;
 8             }
 9         }
10         for(int i=nums.length-1;i>=0;i--) {
11             if(nums[i]==target) {
12                 res[1] = i;
13                 break;
14             }
15         }
16         return res;
17     }
18 }

解法二：

 1 class Solution {
 2     public int[] searchRange(int[] nums, int target) {
 3         int left = 0, right = nums.length - 1;
 4         while (left <= right) {
 5             int mid = left + (right - left) / 2;
 6             if (nums[mid] < target) {
 7                 left = mid + 1;
 8             } else if (nums[mid] > target) {
 9                 right = mid - 1;
10             } else {
11                 // 找到目标值，向左右扩展以找到开始和结束位置
12                 int start = mid, end = mid;
13                 while (start >= 0 && nums[start] == target) {
14                     start--;
15                 }
16                 while (end < nums.length && nums[end] == target) {
17                     end++;
18                 }
19                 // 返回开始和结束位置
20                 return new int[]{start + 1, end - 1};
21             }
22         }
23         // 目标值不存在
24         return new int[]{-1, -1};
25     }
26 }

解法三：

 1 class Solution {
 2 
 3     public int[] searchRange(int[] nums, int target) {
 4         int left = 0;
 5         int right = nums.length - 1;
 6         int first = -1;
 7         int last = -1;
 8         // 找第一个等于target的位置
 9         while (left <= right) {
10             int middle = (left + right) / 2;
11             if (nums[middle] == target) {
12                 first = middle;
13                 right = middle - 1; //重点
14             } else if (nums[middle] > target) {
15                 right = middle - 1;
16             } else {
17                 left = middle + 1;
18             }
19         }
20 
21         // 最后一个等于target的位置
22         left = 0;
23         right = nums.length - 1;
24         while (left <= right) {
25             int middle = (left + right) / 2;
26             if (nums[middle] == target) {
27                 last = middle;
28                 left = middle + 1; //重点
29             } else if (nums[middle] > target) {
30                 right = middle - 1;
31             } else {
32                 left = middle + 1;
33             }
34         }
35 
36         return new int[]{first, last};
37     }
38 
39 }