# Search in Rotated Sorted Array

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

## Normal binary seach

just reciting a binary search code

```
while s < e
mid = (s + e) / 2
if target == A[mid]
return mid
else if target < A[mid]
e = mid
else if target > A[mid]
s = mid + 1
```

## Binary search essential

Each time we separate the numbers into two parts. After the target number compared to the mid number, we are sure which part that the target number must be in.

## Which part the target must be

In this case, there is no duplicate, so the target must be either in left part or right part.

What we need to do is to determine which part.

```
while s < e
mid = (s + e) / 2
if target == A[mid]
return mid
else if on the left
e = mid
else if on the right
s = mid + 1
```

### Brute force

Dont be brainfucked. so just write down all possible `s`

,`m`

,`e`

and `t`

.

`t`

is either on the left side or right side of `m`

.

```
[s t m e]
or
[s m t e]
```

and `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`

(normal binary search)

```
1 E
2 *
3 *
4 *
5 *
6 M
7 *
8 *
9 *
10 S
```

`s`

< `m`

> `e`

```
1 *
2 *
3 M
4 *
5 *
6 *
7 S
8 E
9 *
10 *
```

`s`

> `m`

< `e`

```
1 *
2 *
3 S
4 E
5 *
6 *
7 *
8 M
9 *
10 *
```

`s`

> `m`

> `e`

this is not a sorted array

#### After got all the possible cases

2 (`t`

either on the left or on the right of `m`

) * 3 ( relations of `s`

`m`

`t`

) = 6 cases

each case choose either the left part(`e = m`

) or the right part(`s = m + 1`

) of input array.

You can determine which part to choose by your brain or by accident.

Dont worry, if you choose part by accident, it is at most 64 tries.

### Source code *Read on Github*

```
1 public class Solution {
2 public int search(int[] A, int target) {
3 // Note: The Solution object is instantiated only once and is reused by each test case.
4 int s = 0;
5 int e = A.length;
6
7 while(s < e){
8 int mid = (s + e) /2;
9
10 if(A[mid] == target){
11 return mid;
12 }
13
14 if(target < A[mid]){
15 // normal in first half
16
17 if(A[s] <= A[mid] && A[s] <= target){
18 e = mid;
19 // abnormal
20 }else if(A[mid] <= A[e - 1]){
21 e = mid;
22 }else {
23 s = mid + 1;
24 }
25
26 } else {
27
28 // normal in last half
29
30 if(A[mid] <= A[e - 1] && target <= A[e - 1]){
31 s = mid + 1;
32 } else if(A[s] <= A[mid]) {
33 s = mid + 1;
34 } else {
35 e = mid;
36 }
37
38 }
39 }
40
41 return -1;
42 }
43 }
```