### Description

Given an array of integers `nums`

which is sorted in ascending order, and an integer `target`

, write a function to search `target`

in `nums`

. If `target`

exists, then return its index. Otherwise, return `-1`

.

You must write an algorithm with `O(log n)`

runtime complexity.

### Solution

Prerequisites for using binary search:

- Ordered list
- All elements are unique (if not, the value returns probably is not unique)

For binary search method, one important thing is to clearly define interval’s close and open situation. Usually we have two kinds of intervals:

- Left close and right close [left, right]
- Left close and right open [left, right)

#### For left close and right close [left, right]

Two points:

`while (left <= right)`

should use`<=`

, because it’s meaningful ween`left == right`

since we use [left, right]`if (nums[middle] > target) right`

we need to let`nums[middle] = - 1`

，because we are sure`nums[middle]`

is not our`target`

，so the ending condition is when we come across element with index is -1

```
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
middle = (left + right) // 2 #Floor Division
if nums[middle] < target:
left = middle + 1
elif nums[middle] > target:
right = middle - 1
else:
return middle
return -1
```

#### For left close and right open [left, right)

```
class Solution:
def search(self, nums: List[int], target: int) -> int:
left,right =0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid+1
elif nums[mid] > target:
right = mid
else:
return mid
return -1
```