- Scope of use: the search space is **ordered** within **a certain range**
- Why? Turning On → Ologn
- Goal: To narrow down the search range. (not find the exact target, maybe still need 1-2 comparison)
- key points
- What is the search range(区间)?
- What is the target you are looking for?
```python
# pattern
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
# input an sorted array
# return the index of target, or -1 if target not exist
start = 0
end = len(nums) - 1
# find a range with 2 elements
while start + 1 < end:
mid = (start + end) // 2
if nums[mid] < target:
start = mid
elif nums[mid] > target:
end = mid
else:
return mid
if nums[start] == target:
return start
if nums[end] == target:
return end
return -1
```