题目：
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例：
image.png
思路：
二分查找（二分查找很简单，细节很重要）
通过查找一个数的左边界，可以找到目标数的左边界；
然后查找比目标数大一的数（target = 8 ----> 找8+1）的左边界，这个数的左边界 -1 就是目标数的右边界。
重点：
怎么通过二分查找，找到目标数的左边界？
参考：作者：labuladong
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/er-fen-cha-zhao-suan-fa-xi-jie-xiang-jie-by-labula/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
代码：
int left_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length; // 注意
while (left < right) { // 注意
int mid = (left + right) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid; // 注意
}
}
return left;
}
代码：
class Solution {
public int[] searchRange(int[] nums, int target) {
//查找目标数的左边界
int first = binarySearch(nums, target);
//查找目标数的右边界（即目标数+1的数的左边界-1）
int last = binarySearch(nums, target + 1) - 1;
//如果左边界等于数组长度，即目标数比数组所有数都大
//或者左边界的数不等于目标数，目标数比所有数都小
if (first == nums.length || nums[first] != target) {
//即，找不到目标数，就返回-1
return new int[]{-1, -1};
} else {
//否则，返回左右边界。
return new int[]{first, last};
}
}
//查找左边界的二分查找
public int binarySearch(int[] arr, int target) {
int l = 0;
int h = arr.length;
//注意条件是l<h
while (l < h) {
int mid = l + ((h - l) >>> 1);
if (target <= arr[mid]) {
h = mid;
} else if (target > arr[mid]) {
l = mid + 1;
}
}
return l;
}
}
时间复杂度：O(logn)，空间复杂度：O(1)
