## 1. 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.

Constraints:

1. $$1 \leq nums.length \leq 10^{4}$$
2. $$-10^{4} \lt nums[i], target \lt 10^{4}$$
3. All the integers in nums are unique
4. nums is sorted in ascending order

### 1.1. Examples:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1


## 2. Solution

### 2.1. Understanding the problem

We use Binary Search to achieve O(log n) runtime complexity.

### 2.3. Code

def search(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
ret = -1
left_idx = 0
# why len(nums) - 1?
right_idx = len(nums) - 1

# Why use <=?
while left_idx <= right_idx:
mid_idx = (left_idx + right_idx) // 2
curr = nums[mid_idx]

if target == curr:
return mid_idx
elif target > curr:
left_idx = mid_idx + 1
else:
right_idx = mid_idx - 1

return ret

# tests
nums = [-1, 0, 3, 5, 9, 12]
target = 9
print(search(nums, target) == 4)

nums = [-1, 0, 3, 5, 9, 12]
target = 2
print(search(nums, target) == -1)

nums = [0, 3, 5, 9, 12]
target = 5
print(search(nums, target) == 2)

nums = [0, 3, 5, 9, 12]
target = 2
print(search(nums, target) == -1)

nums = [-1]
target = 1
print(search(nums, target) == -1)

nums = [0]
target = 0
print(search(nums, target) == 0)

True
True
True
True
True
True


#### 2.3.1. Complexity

##### 2.3.1.1. Time complexity:

$$O\log{n}$$, where n=len(nums)

##### 2.3.1.2. Space complexity:

$$O(n)$$

### 2.4. Leetcode solution

nil

<<imports for typing>>



## 3. More analysis

### 3.1. General thoughts

I never knew how to understand the conditions needed in Binary Search.

I have the Binary search key point to help myself memorize the algorithm:

1. 首尾要有效 - Both start and end indexes are valid indexes (can get element from the list)
2. 首尾要相交 - left_idx and right_idx need to converge (==) so that we can handle a list of single element
3. 中点需整除 - Use mod 2 to get the mid point
# why len(nums) - 1?
# because len(nums) - 1 is the last element of the list nums
right_idx = len(nums) - 1

# Why use <=?
# consider a list that only contains a single element,
# then left_idx = 0 and right_idx = 0
# if we don't have the equal sign here,
# we will easily fail this case
while left_idx <= right_idx:


Another point is that for a potentially empty list, we can simply return -1 if the list's length is 0.