# Search in Rotated Sorted Array II

https://leetcode.com/problems/search-in-rotated-sorted-array-ii

## By accident Again

using programming by accient we solved Search in Rotated Sorted Array.

But, this time, We can t sure the target number is on the left or on the right of the `mid`

.

e.g.

```
t = 2
[ 1 1 1 1 1 1 2 1 1 1 1]
s m e
```

this time, we do not know `s = m + 1`

or `e = m`

.

### Brute force again

`s`

`m`

`e`

may be like below. (put == or != between `s`

`m`

`e`

)

`s`

!=`m`

!=`e`

`s`

!=`m`

==`e`

`s`

==`m`

!=`e`

`s`

==`m`

==`e`

`s`

!= `m`

!= `e`

this is handled by Search in Rotated Sorted Array.

`s`

!= `m`

== `e`

```
[ 1 1 1 1 2 2 2 2 2 2 2]
s m e
```

`m`

== `e`

means `m`

.. `e`

are the same number. they are safe to be removed.
Remember, number at `m`

does not equal to `t`

, because we had checked `if A[m] == t`

before.

`s`

== `m`

!= `e`

```
[ 1 1 1 1 1 1 1 2 2 2 2]
s m e
```

this case is the same as `s`

!= `m`

== `e`

`s`

== `m`

== `e`

Wrost case

```
t = 2
[ 1 1 1 1 1 1 2 1 1 1 1]
s m e
```

we only know `t`

does not equal to `s`

`m`

or `e`

.

what we can do it only search again by doing

```
s = s + 1
e = e - 1
```

### Source code *Read on Github*

```
1 public class Solution {
2 public boolean search(int[] A, int target) {
3 int s = 0;
4 int e = A.length;
5
6 while(s < e){
7 int mid = (s + e) /2;
8
9 if(A[mid] == target){
10 return true;
11 }
12
13 if(target < A[mid]){
14 // normal in first half
15 if (A[s] == A[mid]) {
16 if(A[mid] == A[e - 1]){
17 // special
18
19 s++;
20 e--;
21
22 }else{
23 s = mid + 1;
24 }
25
26 } else if(A[s] <= A[mid] && A[s] <= target){
27 e = mid;
28 // abnormal
29 }else if(A[mid] <= A[e - 1]){
30 e = mid;
31 }else {
32 s = mid + 1;
33 }
34
35 } else {
36
37 // normal in last half
38 if (A[mid] == A[e - 1]) {
39 if(A[s] == A[mid]){
40 s++;
41 e--;
42 }else{
43 e = mid;
44 }
45
46
47 } else if(A[mid] <= A[e - 1] && target <= A[e - 1]){
48 s = mid + 1;
49 } else if(A[s] <= A[mid]) {
50 s = mid + 1;
51 } else {
52 e = mid;
53 }
54
55 }
56 }
57
58 return false;
59 }
60 }
```