LeetCode每日一题：search for a range

问题描述

Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
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].

问题分析

这道题没什么难度，就是写完后发现复杂度变成了O(n),若要变成O(logn)的复杂度要把查找部分用二分查找才行，AC之后也懒得改了。

代码实现

public int[] searchRange(int[] A, int target) {
        if (A.length == 1) {
            if (A[0] == target) return new int[]{0, 0};
            else return new int[]{-1, -1};
        }
        int left = 0, right = A.length - 1;
        while (left < right) {
            if (A[left] != target) left++;
            if (A[right] != target) right--;
            if (A[left] == target && A[right] == target) {
                return new int[]{left, right};
            }
        }
        return new int[]{-1, -1};
    }