题目描述

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
给出一个递增的int数组，找到target值的起始和结束位置。

Your algorithm's runtime complexity must be in the order of O(log n).
算法的时间复杂度要求O(log n)。

If the target is not found in the array, return [-1, -1].
如果没有找到target，返回[-1, -1]。

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

思路分析

有序数组，log n时间复杂度内找target，还是二分查找法的用法。这回数组是有重复数字的了，找范围需要找两个数，和二分查找的思路一样，分别用二分查找法找到起点和终点。以nums = [5,7,8,8,8,10], target = 8为例：
找起点时，如果nums[mid] == target，那么说明mid有可能是起点，也有可能是连续的8的中间的某一个，因此先记录mid的位置，然后再去左边查找。如果nums[mid] != target，则和普通的二分查找一样。
找终点是同理。

代码实现

public class Solution {


    /**
     * 88 / 88 test cases passed.
     *  Status: Accepted
     *  Runtime: 8 ms
     *  
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int left = findLeft(nums, 0, nums.length - 1, target);
        int right = findRight(nums, left, nums.length - 1, target);
        return new int[]{left, right};
    }

    private int findLeft(int[] nums, int start, int end, int target) {

        if (start > end) {
            return  -1;
        }

        int result;

        int mid = (start + end) / 2;

        if (nums[mid] == target) {
            result = mid;
            int res = findLeft(nums, start, mid - 1, target);
            if (res != -1) {
                result = res;
            }
            return result;
        } else if (nums[mid] > target) {
            return findLeft(nums, start, mid - 1, target);
        } else {
            return findLeft(nums, mid + 1, end, target);
        }

    }

    private int findRight(int[] nums, int start, int end, int target) {

        if (start < end) {
            return  -1;
        }

        int result;

        int mid = (start + end) / 2;

        if (nums[mid] == target) {
            result = mid;
            int res = findRight(nums, mid + 1, end, target);
            if (res != -1) {
                result = res;
            }
            return result;
        } else if (nums[mid] > target) {
            return findRight(nums, start, mid - 1, target);
        } else {
            return findRight(nums, mid + 1, end, target);
        }

    }

}