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.

--

--

--

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

BigQuery Column-level security with Terraform

Lowest Common Ancestor of a Binary Tree — Day 10(Python)

How many views does an APP make?

Statistics on seaborn plots with statannotations

Make Sure Scrum Fits your Purpose, not Vice Versa. Part 3

Get All The Information About Peppol

The case of iOS OOM Crashes at Compass

Web Scraping: Scraping Table Data

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Annamariya Tharayil

Annamariya Tharayil

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

More from Medium

Build Array from Permutation — Day 103(Python)

10 Key difference between object oriented programming and procedure oriented programming

Introduction to Programming - What is Programming Paradigm?

Min-Max Sum(30 Day Hackerrank Challenge)