# Search in Rotated Sorted Array

ID: 62; medium; 搜索旋转排序数组

Last updated

ID: 62; medium; 搜索旋转排序数组

Last updated

Solution 1 (Java)

Notes

In order to perform a classical binary search, we need to have a strictly increasing or decreasing series. Here, the rotate array can be seen as two increasing arrays. We need to determine which half we should perform the operations on. Thus, we compare the `mid`

element with the first element in the array to see which half the `mid`

element is on currently.

I. The

`mid`

element is on the left halfThe reason is that if the `mid`

element is larger than the first element, by the construction of the rotated array, we know that the `mid`

element is on the left half now. After this first check, we try to see where `target`

is. We compare if the `target`

is on the same half (left half) as the mid element. This comparison is simple checking if `target`

is in between `A[left]`

and `A[mid]`

.

If

`target`

and the`mid`

element are on the same half (`target`

is on the left half), we can discard the right half of the array.If they are on different halves (

`target`

is on the right half), we can discard the left half.

II. The

`mid`

element is on the right halfIf the `mid`

element is smaller than the first element, then it is on the right half. Similarly, we try to see where `target`

is. If `target`

is in between `A[mid]`

and `A[right]`

, then `target`

is on the same half as the `mid`

element (right half).

If

`target`

and the`mid`

element are on the same half (`target`

is on the right half), we can discard the left half of the array.If they are on different halves (

`target`

is on the left half), we can discard the right half.

Example

`[4, 5, 6, 7, 0, 1, 2]`

and `target = 5`

Case I. 1.: The `mid`

element and `target`

are both on the left side. Loop terminates, the index of 5 is returned.

left

right

mid

New Range

4

2

7

`[4, 5, 6, 7]`

4

7

5

`[4, 5]`

left

right

mid

New Range

4

2

7

`[7, 0, 1, 2]`

7

2

0

`[0, 1, 2]`

0

2

1

`[1, 2]`

left

right

mid

New Range

6

5

1

`[6, 7, 0, 1]`

6

1

7

`[6, 7]`

left

right

mid

New Range

0

5

2

`[2, 3, 4, 5]`

2

5

3

`[3, 4, 5]`

3

5

4

4 immediately returned