【解题报告】【lintcode61】 Search for a Range

题意

在一个有序数组中，找到给出的范围值的开始和结束点下标 nlogn的复杂度

解答

看到nlogn和有序数组，那么就能想象到二分查找，但是需要对二分查找做一些改动 当找到目标时不停止，而是继续对左右区间进行二分，并维护找到区间边缘的最小/最大下标 那么，一次二分进行完毕之后，我们就可以得到最大最小的范围了。

代码

public class Solution {
    /** 
     *@param A : an integer sorted array
     *@param target :  an integer to be inserted
     *return : a list of length 2, [index1, index2]
     */
    int max,min;
    boolean flag;
    public int[] searchRange(int[] A, int target) {
        // write your code here
        max = 0;
        min = A.length;
        flag = false;
        search(A,0,A.length - 1,target);
        if (flag)
        return new int[]{min,max};
        else
            return new int[]{-1,-1};
    }
    private void search(int[] A,int l,int r,int target){
        if (l < 0||r >= A.length||l > r)
            return;
        int mid;
        while (l <= r)
        {
            mid = (l + r)/2;
            if (A[mid] > target)
                r = mid -1;
            if (A[mid] < target)
                l = mid +1;
            if (A[mid] == target)
            {
                if (mid > max)
                    max = mid;
                if (mid < min)
                    min = mid;
                flag = true;
               search(A,l,mid-1,target);
               search(A,mid+1,r,target);
                return;
            }
        }

    }
}