题目：

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