Binary Search

Naive Solution

A brute force solution would involve iterating through the entire array and checking each element to see if it matches the target. This is a linear search.

Code

def linear_search(nums, target):
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

Time Complexity

O(n), where n is the number of elements in the array.

Space Complexity

O(1), as it only uses a constant amount of extra space.

Optimal Solution: Binary Search

Since the array is sorted, we can use binary search to find the target in O(log n) time.

1. Initialize left to 0 and right to len(nums) - 1.
2. While left <= right:
   • Calculate the middle index: mid = (left + right) // 2
   • If nums[mid] == target, return mid.
   • If nums[mid] < target, the target must be in the right half, so update left = mid + 1.
   • If nums[mid] > target, the target must be in the left half, so update right = mid - 1.
3. If the loop finishes without finding the target, return -1.

Code

def binary_search(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Time Complexity

O(log n), where n is the number of elements in the array. This is because binary search halves the search space in each iteration.

Space Complexity

O(1), as it only uses a constant amount of extra space.

Edge Cases

• Empty Array: If the input array nums is empty, the algorithm should return -1 immediately.
• Target Smaller Than First Element: If the target is smaller than the first element of the array, it cannot exist in the array, so the algorithm should return -1.
• Target Larger Than Last Element: If the target is larger than the last element of the array, it cannot exist in the array, so the algorithm should return -1.
• Target Exists Multiple Times (Although the problem states unique integers): The algorithm will return the index of one of the occurrences, but not necessarily the first one. If the requirement was to find the first occurrence, the algorithm would need to be modified to continue searching the left half after finding a match.