A complete analysis of this question, with and without duplicate

  • 0

    Let the array be A and the size be n, and we assume n > 1 as otherwise it is trivial. The number is indiced from 0 to n-1, and can be accessed via A[i] for 0 <= i <= n - 1.

    There are two variants of this question. First and easier, there is no duplicate. Second and much harder, there exists duplicate. The first case is solved with a simple binary search, finishing with O(log n) worse-case complexity. While still upon a binary search, the second variant requires O(n) worse-case complexity. A worse case is immediately given, 1,1,1,1,1,1,..., 0,1,1,...,1, in which we cannot decide the answer until each number is seen at lease once.

    Let's first discuss the answer for the non-duplication case. For simplicity, we first rule out where these is not rotation by easily comparing A[0] and A[n-1]. Then we pick up the first item as the pivot and process the binary-search over the rest array. Below is the pseudo code.

    Algorithm for the Find min in rotated sorted array

    Let's show the algorithm is correct. We use t to denote the pivot, b to denote the value at begin, x to denote the min value and e to denote the value at end. Further, we denote the mid-indiced (between begin and end) value as m. In the array, they distribute like (tb...x...e). There are four cases:
    (1) x != b and x != e. The right order would then be (x...etb...). Immediately, x < e < t < b.
    (2) x = b and x != e. b is the smallest value, and we have x < e < t.
    (3) x = e and x != b. e is the smallest value, and we have x < t < b.
    (4) x = b = e. In this case, there are only two values in the array.

    It is easy to find that the algorithm closes case 4 by triggering only one loop. We extend the discussion for case 1. There are three positions for the m, (1) (tb... (m) ... x ... e); (2) (tb... x(m) ... e); (3) (tb... x ... (m) ... e). According to the algorithm, if m positions (1), b will move to the place of m; if m positions (3), e will move to the place of m; As a result, the search space will be narrowing down exponentially. And b and e finally encounter around x, as clearly both b and e never go trespassing x. When mid = begin, it is clear that begin = end or begin = end - 1, and we know that one of b and e must be the target. For case 2, it is clear that e will be pushed in every step towards x, analogously for case 3 where b approaches x, the algorithm covers these cases.

    It is much complicated when duplicate is allowed. Let's still take case 1 from above and look into the three positions of m. If A[mid] < t and A[mid] < t, things just go as usual. However, it is possible now A[mid] = t, and this is the sticking point. All positions of m do not deny the possibility of A[mid] = t, and hence we cannot jump either from b to m or from e to m, as for example if jumping from b to m, and m positions (3), we will jump over the target x and never gonna find it. We hence come up with an idea to switch target to b, and process the binary search again on the new target in the range from begin + 1 to end. After the switch, we will immediately return t as the target if t <= b and t < e (note that t <= b is clearly necessary when t is the minimum value). Next we show this is true by drawing contradiction. Suppose there is x between begin (note that this is the new begin) and end, such that x < t. We then have (tb... x ... e), in which the rotated point is x, and the correct order would be (x ... e tb...), rendering e <= t, and clearly a contradiction.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.