704 Binary Search

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.2. Algorithm

2.3. Code

Listing 1: 704 Binary Search my solution

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)

Listing 2: 704 Binary Search my solution-results

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

Listing 3: 704 Binary Search leetcode solution

<<imports for typing>>

Listing 4: 704 Binary Search leetcode solution-results

2.4.1. Time complexity:

2.4.2. Space complexity:

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.

3.2. Related problems

1. [BROKEN LINK: idid:6705fa69-9835-4076-b293-cd962e3c5828]

4. Log time