34. Search for a Range (Medium) LinkedIn

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order ofO(logn).

If the target is not found in the array, return[-1, -1].

For example,
Given[5, 7, 7, 8, 8, 10]and target value 8,
return[3, 4].

Solution 1: Binary Search O(log n); O(1) 九章模板，很好用

使用两次二分查找法，第一次找到左边界，第二次调用找到右边界即可

    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) return new int[]{-1, -1};
        int start = findFirst(nums, target);
        if (start == -1) return new int[]{-1, -1};
        int end = findLast(nums, target);
        return new int[]{start, end};
    }

    public int findFirst(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;
            if (nums[mid] < target) { //第一个位置在右边
                start = mid;
            } else {
                end = mid;
            }
        }
        if (nums[start] == target) return start;
        if (nums[end] == target) return end;
        return -1;
    }

    public int findLast(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;
            if (nums[mid] > target) { // < 换成 > //最后一个位置在左边
                end = mid; //start换成end
            } else {
                start = mid; //end换成start
            }
        }
        //下面start和end判断位置交换，先判断end，因为是找最后一个位置
        if (nums[end] == target) return end;
        if (nums[start] == target) return start;
        return -1;
    }