Binary Search — Day 14(Python)

Photo by Cam Morin on Unsplash

Today we will be visiting one of the questions from Leetcode’s daily coding challenge October edition.

704. Binary Search

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.

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

Note:

1. You may assume that all elements in nums are unique.
2. n will be in the range [1, 10000].
3. The value of each element in nums will be in the range [-9999, 9999].

Binary search is a simple algorithm and takes advantage of the fact that elements are sorted in the given array. Let us look into the algorithm.

1. Initialize low as the start of the list that is 0, and high as the length of the list.
2. Find the index of the middle position of the list. If the mid index is equal to the target, return the mind index.
3. If the target value is lesser than the element at the middle index, we will focus on the numbers in the first half of the list. We will change the value of high to mid -1, and perform a binary search again.
4. If the target value is greater than the element at the middle index, we will focus on the numbers in the second half of the list. We will change the value of low to mid +1, and perform a binary search.
5. Follow steps from 2 to 4, until low is lesser than high.

class BinarySearcher:
    def search(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums)-1
        while(low<=high):
            mid = (low + high)//2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                low = mid + 1
            else:
                high = mid -1
        return -1

Complexity Analysis

Time Complexity

Every time we look for the target on our list, we are dividing our list by half. Hence time complexity is O(logN), where N is the number of elements in our list.

Space Complexity

We are making use of constant space while we perform binary search and hence space complexity is O(1).

I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.