🔦704. Binary Search

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 <= nums.length <= 104

• -104 < nums[i], target < 104

• 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

SOLUTION

The title of the question clearly states "binary search", so, we will use binary search to see if the target exists in our list. You can solve this easily by iterating over every element once but that would be linear time (O(n)) and not O(log n). Therefore our only option is a binary search. The binary search algorithm works by dividing the list in half and checking if the target is on the left or right side. If the target is not in the middle, we can repeat this process until we find the target or run out of the list to divide it in half. This algorithm has a run time of O(log n) where n is the length of the list. *Note: this will only work when the list is sorted.

We will first calculate the midpoint(left+(right-left)//2) of the list to divide it into two halves. If the midpoint is not the target element, we will compare the midpoint value to the target. If the target is greater than the midpoint, we know that we have to take the right half of the list. Otherwise, we will take the left half of the list. The bisecting of the list allows us to shrink the search space into half the next time we repeat the process.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # we need the two ends to calculate the mid point
        left = 0
        right = len(nums)-1
        
        while left <= right: 
            # mid point
            mid = left + (right - left) // 2
            
            if nums[mid] == target: 
                return mid
            
            # given the list is sorted, we only have to look at one side of the mid point. 
            
            # we only care about the left side of the midpoint
            elif nums[mid] > target: 
                right = mid - 1
            
            # we only care about the right side of the midpoint
            else: 
                left = mid + 1
        
        return -1

TIME AND SPACE COMPLEXITY

TIME: O(log n) we halve the list every time we look for the target. This is O(log n)

SPACE: O(1) regardless of the list size, we will only need three variables: left, right and mid. Therefore, space is constant.