Question

link

Stats

Frequency	3
Difficulty	5
Adjusted Difficulty	4
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This one is based on the solution of previous question.

The previous question is already very difficult, both the logic and coding part. However, if you solve previous question by yourself, you will do this one easily.

I will pick the 2nd piece of code in previous question, and modify it to solve this problem.

Solution for previous question:

public int search(int[] A, int target) {
    int left = 0;
    int right = A.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (target == A[mid]) return mid;
        if (A[left] <= A[mid]) {
            if (A[left] <= target && target <= A[mid]) right = mid;
            else left = mid + 1;
        } else {
            if (A[mid] <= target && target <= A[right]) left = mid;
            else right = mid - 1;
        }
    }
    return -1;
}

Solution

My solution is to skip all duplicated numbers before the while-loop.

The most standard solution is left-pointer incremental. A good code is written from this blog.

Code

First, my solution

public boolean search(int[] A, int target) {
    int len = A.length, L = 0, R = len - 1;
    if (A[L] == A[R]) {
        int duplicate = A[R];
        if (duplicate == target) return true;
        while (L < len && A[L] == duplicate) L ++;
        while (R >= 0 && A[R] == duplicate) R --;
    }
    while (L <= R) {
        // Avoid overflow, same as M=(L+R)/2
        int M = L + ((R - L) / 2);
        if (A[M] == target) return true;
        // the bottom half is sorted
        if (A[L] <= A[M])
            if (A[L] <= target && target < A[M]) R = M - 1;
            else L = M + 1;
        // the upper half is sorted
        else 
            if (A[M] < target && target <= A[R]) L = M + 1;
            else R = M - 1;
    }
    return false;
}

Second, standard solution

public boolean search(int[] A, int target) {
    int len = A.length, L = 0, R = len - 1;
    while (L <= R) {
        int M = L + ((R - L) / 2);
        if (A[M] == target) return true;
        if (A[L] < A[M])
            if (A[L] <= target && target < A[M]) R = M - 1;
            else L = M + 1;
        else if (A[L] > A[M])
            if (A[M] < target && target <= A[R]) L = M + 1;
            else R = M - 1;
        else L ++;
    }
    return false;
}