# Leetcode 287 - Find the duplicate number

`Note:`

- We need
`binary search`

but apparently, we cannot do that on`nums`

because it’s not sorted. - By the definition, the range
`[1, n]`

can be the target of binary search. - Find
`middle`

, then iterate through`nums`

, and record num that are`smaller`

than`middle`

. - If
`count`

is strictly bigger than`middle`

, it means there must be more than`middle`

number between`[1, middle]`

. So the repetitve num must be inside. So, move`right = middle`

. - If
`count <= middle`

, we can say there is def no repetitve num between`[1, middle]`

. Move`left = middle + 1`

.

`Question:`

Given an array of integers `nums`

containing `n + 1`

integers where each integer is in the range `[1, n]`

inclusive.

There is only one repeated number in `nums`

, return this repeated number.

You must solve the problem without modifying the array `nums and`

uses only constant extra space.

`Example:`

1 | Input: nums = [1,3,4,2,2] |

`Code:`

1 | /** |