Binary Search — Day 14(Python)
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
n elements and a
target value, write a function to search
target exists, then return its index, otherwise return
Input: nums = [-1,0,3,5,9,12], target = 9
Explanation: 9 exists in nums and its index is 4
Input: nums = [-1,0,3,5,9,12], target = 2
Explanation: 2 does not exist in nums so return -1
- You may assume that all elements in
nwill be in the range
- The value of each element in
numswill be in the range
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.
- Initialize low as the start of the list that is 0, and high as the length of the list.
- Find the index of the middle position of the list. If the mid index is equal to the target, return the mind index.
- 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.
- 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.
- Follow steps from 2 to 4, until low is lesser than high.
def search(self, nums: List[int], target: int) -> int:
low = 0
high = len(nums)-1
mid = (low + high)//2
if nums[mid] == target:
elif nums[mid] < target:
low = mid + 1
high = mid -1
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.
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.