Problem Statement

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, return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Additional information

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i], target <= 10^4
• All the integers in nums are unique.
• nums is sorted in ascending order.

Example 1:

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9

Output: 4

Explanation: 9 exists in nums and its index is 4.

Example 2:

Input: nums = [-1, 0, 3, 5, 9, 12], target = 2

Output: -1

Explanation: 2 does not exist in nums so return -1.

Linear Scan (Brute Force)

Intuition
The simplest way to find an element is to check every single element in the array one by one. We start from the first element and iterate through the entire array. If we find the target, we return its index. If we reach the end without finding it, we return -1.

Algorithm

1. Iterate i from 0 to len(nums) - 1.
2. If nums[i] == target, return i.
3. If the loop finishes, return -1.

def search(nums: list[int], target: int) -> int:
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

Time & Space Complexity

• Time complexity: O(n)

• Reason: We verify every element once.

• Space complexity: O(1)

• Reason: No extra space used.

Binary Search (Optimal)

Intuition
Since the array is sorted, we can discard half of the array at each step. We start by checking the middle element.

• If the middle element is the target, we are done.
• If the target is smaller than the middle element, we know the target must be in the left half (since the right half only contains larger numbers).
• If the target is larger, it must be in the right half.
  We repeat this process until the search space is empty.

Algorithm

1. Initialize l (left) to 0 and r (right) to len(nums) - 1.
2. While l <= r:

• Calculate the middle index mid = (l + r) // 2.
• If nums[mid] == target, return mid.
• If nums[mid] < target, move the left pointer to mid + 1 (search right half).
• If nums[mid] > target, move the right pointer to mid - 1 (search left half).

3. Return -1.

def search(nums: list[int], target: int) -> int:
    l, r = 0, len(nums) - 1
    
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            l = mid + 1
        else:
            r = mid - 1
            
    return -1

Time & Space Complexity

• Time complexity: O(log n)

• Reason: At each step, the search space is cut in half.

• Space complexity: O(1)

• Reason: We only use a few variables for pointers.