題目：

給定一個按照升序排列的整數數組 nums，和一個目標值 target。找出給定目標值在數組中的開始位置和結束位置。

你的算法時間復雜度必須是 O(log n) 級別。

如果數組中不存在目標值，返回 [-1, -1]。

示例：

image.png

思路：

二分查找（二分查找很簡單，細節(jié)很重要）
通過查找一個數的左邊界，可以找到目標數的左邊界；
然后查找比目標數大一的數（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）
著作權歸作者所有。商業(yè)轉載請聯系作者獲得授權，非商業(yè)轉載請注明出處。

代碼：

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)