34.在排序数组中查找元素的第一个和最后一个位置

题目描述：

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-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 };
        }
        // 满足条件时，只需要返回开始位置和结束位置，即链表的头元素和尾元素
        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;
        // 用于存放结果
        int rs[] = new int[2];
        while (low <= high) {
            int mid = (low + high) / 2;
            // mid和target相等
            if (nums[mid] == target) {
                // 循环查找开始位置的下标
                while (low < mid) {
                    if (nums[low] == target) {
                        // 相同时，存入开始位置的下标
                        rs[0] = low;
                        // 结束
                        break;
                    } else {
                        // 不相同时，low增加
                        low++;
                    }
                }
                // 循环查找结束位置的下标
                while (mid < high) {
                    if (nums[high] == target) {
                        // 相同时，存入结束位置的下标
                        rs[1] = high;
                        // 结束
                        break;
                    } else {
                        // 不相同时，high减少
                        high--;
                    }
                }
                // 返回开始位置和结束位置
                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 };
    }