Binary Search - Data Structures & Algorithms Tutorial Python #13

Binary search is a popular search algorithm that can find an element using log(n) time complexity. In this video we will go over theory behind binary search, compare it with linear search and then implement binary search in python.

Topics

00:00 Overview
00:22 Theory behind linear search
02:23 Theory behind binary search
05:50 Python code for binary search
15:40 Performance comparison (linear vs binary search)
18:30 Recursive binary search
23:47 Exercise

#binarysearch #datastructures #algorithms #python

DISCLAIMER: All opinions expressed in this video are of my own and not that of my employers'.

[priscillacheng]

I love your witty quips! "If you click 'solution' too early, you will get a computer virus" lol I find myself looking forward to them every video. Thanks for making this!

[akashp]

underrated video. you're the best teacher for me in Data structures and Algorithm. the way you think is the way i also think so i end up with doubts like why and hows, which you clear at the exact same time. Thank you

[thudfactory]

You are one of the best tutors on youtube for Computer Science, love and respect from Bangladesh.

[pavanpatro]

Firstly, simplistic yet awesome!! explanation..
A scenario expressing out of curiosity (more from performance perspective) : "Let's assume a scenario, where the input list of numbers doesn't follow any particular order i.e. ascending/descending.. then sorting of the list first, prior to performing the binary search enhances the code performance.

[tharindusathsara]

Really very happy about finding such an obvious and understood funny video series about data structures and algorithms. Everything is 100% clear with deeply explained theories and well-understood practicals. Also, the exercise series with the videos are highly appreciated. Dear sir thank you so much for the fantastic video series. ❤💖

[snehakurhade]

The recursion code errors because when you call the function in the main, the right index is provided as len(number_list) which is 8 in your case.
Instead the right index should be initialized with (len(number_list)-1). Thus your right index now correctly points to location 7 which consists of value 67

[winnienakimuli]

Thank you so much Sir for this series of videos, they have helped a lot being a newbie at these topics, and the debugging tip is everything, thank you!

[jykw]

Sir you getting error at the end because you didn't len(numbers_list)-1 for recursive binary search input?

[zubair]

Hello @codebasics thanks for very good explaination but i want to add one thing in "binary_search_recursive" function you don't need to handle
if mid_index >= len(numbers_list) or mid_index < 0:
return -1
just provide right_index correct like you are providing right_index = len(numbers_list) but it should be len(numbers_list)-1

[kameshparashar]

Waiting for this video from a long time ❤️

[anilvenkatesh]

Thank you @codebasics, requesting you to kindly continue this series of Data Structures and Algorithms in Python sir. This is really good and very helpful for beginners who aim to go from zero to hero. Thank you once again sir.

[ThaoPhuong-lnvc]

Need help understanding big O:

1. What is the average time complexity of the 2nd exercise solution?
My answer is O(log n + left + right), where left + right <= n.
- The best case is O(log n): only 1 occurrence
- The worst case is log(n): the number of occurrences = length of the input array
- Average case: ??? -- I don't know

2. Another approach would be using a Hash Table, but that solution would have the time and space complexity of O(n) because we have to go through each number and add it to the hash table (value : occurrence(s)). So my guess is finding the max occurrences using binary search is still better. Am I on the right train of thought?

3. What is the best solution for this exercise?

Any suggestions, clarification, and answers would be much appreciated!

[Whitris]

Kudos for your courses! Just a thing: it would be better to use time.perf_counter() inside the time_it decorator, instead of time.time(). You would get a much better resolution, avoiding the "0.0 mil sec" measurement for the binary search

[lisamathur]

Another approach to solve with bin_serarch_rec -
def bin_search_rec(numbers, key):

l = 0
u = len(numbers) - 1
mid = (u+l)//2
if numbers == []:
return False
if numbers[mid] == key:
return True
if numbers[mid] > key:
return bin_search_rec(numbers[0:mid], key)
if numbers[mid] < key:
return bin_search_rec(numbers[mid+1 : ], key)

[sachinladhad]

Dear Sir,

You are the best teacher, I am really enjoy videos and learning at the age of 45.

[AACREATIONS]

best and best lecture ever i have seen till now..thank you sir

[rafeeqsyedamjad]

Sir plz continue this series ds and algo with python
online we have fewer resources to follow ds and algo with python it will be really helpful to crack product based companies for data science. upload videos related to this as much as possible

[globemasterybusinessformul]

Your explanation is very clear and practical

[abhishekkumaryadav]

please continue this series...you explanation is great.

[andrewmukare]

I loved this tutorial! You are a great teacher! Thank you!