# Leetcode 81 - Search in rotated sorted array II

`Note:`

- Find the
`middle = left + right / 2`

. - But because it has
`duplicates`

, when`nums[left] == nums[right] == nums[middle]`

,- Such as
`[1,1,1,2,1,1,1,1,1,1,1]`

or`[1,1,1,1,1,1,1,1,2,1,1]`

with target`2`

. - There is no way we can tell
`2`

is on the`left`

of middle or`right`

.

- Such as
- What should we do?
- Move both
`left`

and`right`

by 1.

- Move both
- Use
`nums[midlle] <= nums[right]`

to check which part the middle is in. - We should use
`<=`

as the condition of`while`

so that we donâ€™t need an extra check on`nums[left] === target`

.

`Question:`

There is an integer array `nums`

sorted in `non-decreasing`

order (not necessarily with distinct values).

Before being passed to your function, `nums`

is rotated at an unknown pivot index `k`

(`0 <= k < nums.length`

) such that the resulting array is `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]`

(0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array `nums`

after the rotation and an integer `target`

, return `true`

if target is in nums, or `false`

if it is not in nums.

You must decrease the overall operation steps as much as possible.

`Example:`

1 | Input: nums = [2,5,6,0,0,1,2], target = 0 |

`Code:`

1 | /** |