I've feel struggle for binary search questions for a long time, and I find a good article for helping me out. Based on the article, followings are how I solve the problem.

- from
`[1, ... , n]`

, after applying`-guess()`

to all the elements, it's actually an array with value`[-1, ..., 0, 1, ...., 1]`

, (`[0, 1,...1]`

if target is 1 and`[-1, ,..., 0]`

if target is n) if we applied`-guess(v)`

* the questions is somehow misleading, it should describes as guess(v) return -1 when you**should lower**your number. - Since there exist one and only one target in the array, we can actually write it in both lower and upper bound style.

### lower bound style

when doing the lower bound style, after applying the predication function, you need to make the array looks like [false, false, ..., true, true, true...true], and you want to find the **first** true.

```
low, high, predicate = 1, n, lambda v: -guess(v) >= 0
bestSoFar = None
while low <= high:
v = low + (high - low) / 2
if predicate(v):
bestSoFar = v
high = v - 1
else:
low = v + 1
return bestSoFar
```

### Upper Bound Style

when doing the upper bound style, after applying the predication function, you need to make the array looks like [true, ..., true, false, ..., false], and you want to find the **last** true.

```
low, high, predicate = 1, n, lambda v: -guess(v) <= 0
bestSoFar = None
while low <= high:
v = low + (high - low) / 2
if predicate(v):
bestSoFar = v
low = v + 1
else:
high = v - 1
return bestSoFar
```