題目描述：

給定一個按照升序排列的整數(shù)數(shù)組 nums，和一個目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。
你的算法時間復(fù)雜度必須是 O(log n) 級別。
如果數(shù)組中不存在目標(biāo)值，返回 [-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(n)

public static int[] searchRange(int[] nums, int target) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                // 直接查詢，滿足條件的就存入list
                list.add(i);
            }
        }
        // 都不滿足條件時，直接返回兩個-1
        if (list.size() == 0) {
            return new int[] { -1, -1 };
        }
        // 滿足條件時，只需要返回開始位置和結(jié)束位置，即鏈表的頭元素和尾元素
        return new int[] { list.get(0), list.get(list.size() - 1) };
    }

O(lgn)

public static int[] search1(int[] nums, int target) {
        // 采用二分法，
        int low = 0, high = nums.length - 1;
        // 用于存放結(jié)果
        int rs[] = new int[2];
        while (low <= high) {
            int mid = (low + high) / 2;
            // mid和target相等
            if (nums[mid] == target) {
                // 循環(huán)查找開始位置的下標(biāo)
                while (low < mid) {
                    if (nums[low] == target) {
                        // 相同時，存入開始位置的下標(biāo)
                        rs[0] = low;
                        // 結(jié)束
                        break;
                    } else {
                        // 不相同時，low增加
                        low++;
                    }
                }
                // 循環(huán)查找結(jié)束位置的下標(biāo)
                while (mid < high) {
                    if (nums[high] == target) {
                        // 相同時，存入結(jié)束位置的下標(biāo)
                        rs[1] = high;
                        // 結(jié)束
                        break;
                    } else {
                        // 不相同時，high減少
                        high--;
                    }
                }
                // 返回開始位置和結(jié)束位置
                return new int[] { low, high };
            } else if (nums[mid] >= target) {
                // mid大，high提前
                high = mid - 1;
            } else {
                // mid小，low提高
                low = mid + 1;
            }
        }
        // 都不滿足條件時，直接返回兩個-1
        return new int[] { -1, -1 };
    }