题目描述

给定一个有序数组，在数组中找到目标值的起始和终止下标，不存在返回 [-1,-1]。
要求时间复杂度为 o(lg(n))。
例子： arr: [1,3,4,5,6,6,6,7] , target: 6；return: [4,6]

解体思路

数组有序查找，时间复杂度为 lg N，根据这两句话，很容易想到二分法。但在查找到一个元素后，不可向前向后遍历获取起始和终止下标，当数组中大部分元素相同且正好为target时，时间复杂度变为线性级别。

可以多次使用二分法查找，确定边界。

public class Search {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 4, 5, 6, 6, 6, 7};
        int target = 6;
        System.out.println(Arrays.toString(search(arr, target)));
    }

    public static int[] search(int[] arr, int target) {
        int lt = 0;
        int[] res = new int[]{-1, -1};

        while (lt < arr.length) {
            int idx = binarySearch(arr, lt, arr.length - 1, target);
            if (idx == -1) {
                break;
            } else {
                res[1] = idx;
                lt = idx + 1;
            }
        }
        int gt = arr.length - 1;
        while (gt > 0) {
            int idx = binarySearch(arr, 0, gt, target);
            if (idx == -1) {
                break;
            } else {
                res[0] = idx;
                gt = idx - 1;
            }
        }


        return res;
    }

    public static int binarySearch(int[] arr, int lo, int hi, int target) {

        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (target > arr[mid]) {
                lo = mid + 1;
            } else if (target < arr[mid]) {
                hi = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}