leetcode--Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":

What

if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

<code>public</code> <code>class</code> <code>Solution {</code>

<code>    </code><code>public</code>

<code>boolean</code> <code>search(</code><code>int</code><code>[] A,</code><code>int</code>

<code>target) {</code>

<code>        </code><code>boolean</code>

<code>isIn =</code><code>false</code><code>;</code>

<code>        </code><code>int</code>

<code>index = findMin(A);    </code>

<code>        </code><code>if</code><code>(index ==</code><code>0</code><code>)</code>

<code>            </code><code>isIn = (Arrays.binarySearch(A,</code><code>0</code><code>, A.length, target) &gt;=</code><code>0</code><code>);</code>

<code>        </code><code>else</code>

<code>            </code><code>isIn = (Arrays.binarySearch(A,</code><code>0</code><code>, index, target) &gt;=</code><code>0</code><code>)</code>

<code>                    </code><code>|| (Arrays.binarySearch(A, index, A.length, target) &gt;=</code><code>0</code><code>);</code>

<code>        </code><code>return</code>

<code>isIn;</code>

<code>    </code><code>}</code>

<code>static</code> <code>int</code> <code>findMin(</code><code>int</code><code>[] A){</code>

<code>i = A.length -</code><code>1</code><code>;</code>

<code>        </code><code>for</code><code>(; i &gt;</code><code>0</code><code>; --i){</code>

<code>            </code><code>if</code><code>(A[i] &lt; A[i -</code><code>1</code><code>])</code>

<code>                </code><code>break</code><code>;</code>

<code>        </code><code>}</code>

<code>i;</code>

<code>}</code>