34. Search for a Range

    /*
     * 34. Search for a Range 
     * 2016-4-19 by Mingyang 注意，这里是二分查找，才是logn
     * 这道题目的难点就在于我们不是一个iteration就找到了答案
     * 而是一共经过了三个，先找到中间那个合适的点，再分别从左边和右边延展找到最正确的点
     */
    public static int[] searchRange(int[] A, int target) {
        int[] res = { -1, -1 };
        if (A == null || A.length == 0)
            return res;
        // first iteration, find target wherever it is
        int low = 0;
        int high = A.length - 1;
        int pos = 0;
        while (low <= high) {
            int mid = (low + high) / 2;
            pos = mid;
            if (A[mid] > target)
                high = mid - 1;
            else if (A[mid] < target)
                low = mid + 1;
            else { // 这个else就是一旦找到了这个target在这个里面就做以下的事情
                res[0] = pos;
                res[1] = pos;
                break;
            }
        }
        if (A[pos] != target)
            return res;
        // second iteration, find the right boundary of this target
        int newlow = pos;
        int newhigh = A.length - 1;
        while (newlow <= newhigh) {
            int newmid = (newlow + newhigh) / 2;
            if (A[newmid] == target)
                newlow = newmid + 1;
            else
                newhigh = newmid - 1;
        }
        res[1] = newhigh;
        // third iteration, find the left boundary of this target
        newlow = 0;
        newhigh = pos;
        while (newlow <= newhigh) {
            int newmid = (newlow + newhigh) / 2;
            if (A[newmid] == target)
                newhigh = newmid - 1;
            else
                newlow = newmid + 1;
        }
        res[0] = newlow;
        return res;
    }