Binary Search Algorithm: Explanation and Python Tutorial
Вставка
- Опубліковано 28 жов 2024
- Binary search is the powerhouse of computer science... Pretty much. One of the most basic introductory concepts in algorithms is binary search, but don't be fooled, binary search is incredibly powerful. Basically, the idea behind it is you are given a (sorted) list of items, you can leverage the sorted-ness to determine where something is much faster than scanning the whole list.
Let's start with guessing a random number between 1 to 10. One way we could do it is to scan the entire list one at a time.. 1, 2, 3... until we get to the right number. But, this is slow! Instead, we can use the computer's feedback to cut down the possibility space in half every time, if we start guessing from the middle. This is what we call divide-and-conquer. The whole gist of binary search is based on this principle.
In a sorted list, we can first guess the middle element and after receiving feedback, we can narrow down the possibilities to either side of that element (if it's not that element itself). We repeat this process until we have either found the element or determined that it's not present.
If our list is "n" elements long, binary search only takes a maximum of log(n) tries to find the answer, whereas linear (naive) search takes a maximum of n tries and average of n/2 tries. This means.. for a list of 1000 items, binary search takes 10 tries when linear search takes on average 500, but could take up to 1000 (and that's assuming the value you're looking for is in the list)!!
Understood? Good. Now we'll code it up and I'll show you exactly how much faster binary search is, compared to naive search!
Link to code: github.com/kyi...
Feel free to leave any questions.
Please consider subscribing if you liked this video: www.youtube.co...
Thanks for watching everyone!
~~~~~~~~~~~~~~~~~~~~~~~~
Follow me on Instagram: / kylieyying
Follow me on Twitter: / kylieyying
Check out my website: www.kylieying.com
Thanks for watching!! Hope this video helped you guys learn something new :)
Hot, i mean binary search is hot 🔥🔥🔥
Do more videos of Data Structures!!
Super duper fan of ur tutorials!!! Where U been all my life?? Lol great work Kylie🙌🏽
thank pretty lady
Im following you around 👀
New series on Algorithms with Python Please...
Really good explanations and I love it.
you're incredible!! I have a computer science exam in 4 days and you just saved my life !!
The way you edit your is Very unique. I love that. Thanks for the explanation. Also I have been following your 12 python project video and it's just amazing..
Again thanks for the efforts.
Not sure why the heck you have
Easy & outstanding explanation. 😍 I tried a lot in UA-cam to find an easy explanation of BST, but today my fighting with myself had ended up here. Thank You so much ☺️
Another great video.... Love your contents
1 minue in, and i now understand binary search! Thanks Kylie
I thoroughly enjoyed this video, thanks for taking the time to make it. I think what you are doing here is going to be a great, best of luck with it all, looking forward to what's next!
Learnt something about efficiency today. Many thanks!
Excellent video Kylie 👏🏻👌!
Wonderful video, explain every single concept in it , great work
I've started learning c, but haven't touched python a bit. Still, I could understand the logic behind your code. Programming is starting to get fun for me.
To be frank, Python is easy, many people can just read it like English.
Thanks ❤️.
You are the best instructor.
Can you create an algorithm series? Your videos are easy to follow and help me learn new things.. ?
So Helpful and Informative; Thanks A Shitload Sweetie, Love you and your Neural Circuits!!!
Your awesome Kylie. Another great video Hun. Thanks 🥰
This is a really great explanation!
This is clear explained! Thank you
I really love your content, please make it a little more consistent. I'll really appreciate it and Also Thanks a lot for making such an amazing content.
Oh thank you .now I understand it🙏
Wow I'm a huge fan
Please make a course on full DSA
Found this very helpful, can you please do more of this :)
Sick video!!! You’re a great teacher!!!!!
Thank you for your efforts and videos. I have question. In the way I learn it is easier to understand a concept if it can be applied to an everyday activity. When would a person use such a search? I am sorry if my questions is basic, but I hope to understand more. Thank you again.
Can't we get a kind of full course on algorithms?
Great tip
Thanks!
Code squad!
Nice vidéo thx.
👍👍👍
Pretty sure I copied everything verbatim and it’s not working. Anyone else, or ideas where I can check the code? Thank you
This is informative! Kindly share the codes here. I have tried to run but it is giving me errors. Please share the codes here
Great
Hey you look awesome and the way you reach out to us❤️ falling in love hahaha thank u for the video
ugh omg kylie so frustrated had to hop here because this is where i learned recursion... the thing i am encountering with it is im doing two versions of Egyptian Fractions: a simple one, one with recursion, and one with memoization (eventually)... im expecting the recursion version to be a lot faster than the first one... but its so slow. kylie or anybody, if you have time, maybe take a look? the simple version can handle complex fractions but the recursion version just chokes easily. moreso, is recursion even the best way to do this Egyptian Fraction problem? memoization is useless cus the repetitive process of Egyptian fractions is unique everytime (or not?)
import time
from fractions import Fraction
def egyptian_frac(x,y): #x is numerator, #y is denominator
if x < y:
given = x/y
answer = []
n = 2
one_over_n = Fraction(1/n).limit_denominator()
while given != 0:
if one_over_n
Love these videos! Thank you for your gracious wisdom!
I like ur eys
First one
BOGO sort best sort.
hmmm... real world... you'll never know if the answer is higher or lower, so principle is moot! Since when is searchable data sorted? And if it were, why would you need to search sorted data?? i love you, but this all seems trivial and useless to me.
That's a very good question! Let me try to answer as best as I can.
The principle here is just the idea of discarding half the search space each time you search because of some special property you can take advantage of (it just so happens in the guessing game we know if an answer is higher or lower). Now, usually we aren't guessing a computer's random number, but we actually do sometimes have sorted data that we need to work with, and I think you'd be surprised how much searchable data is sorted!
Here are some examples: if you've collected someone's tweets for the past year, they would probably be in chronological order. Suppose you want to now figure out if they tweeted on July 4th.. How do you figure out where July 4th is in the data? Without any other knowledge (such as rate of tweeting - what if they tweeted a lot in the first 3 months of the year, or lost their password halfway through the year), we can't really make any assumptions about where in the list this tweet would be if it even exists (so we can't be like "oh it would probably be in the middle of the data"). Then, the most efficient way to search this would be binary search! Some other examples I can think of right now: the English dictionary - we want to find the definition of some word; database IDs - let's say we have a database of users, that is sorted by ID, and we want to find some user with ID xxxx.. actually when you query a database in general, sometimes you have the option of sorting by a specific item, then you may want to perform a search later on with that data; in cs, we also have a data structure called a binary search tree, which is often stored in memory as an array of some sort (no pun intended lol), and this array is typically sorted, this would use binary search to find an item in the tree.
You could also argue that these examples might not be totally "realistic". The purpose of binary search is that in the case where you are given access to a sorted array, you can leverage it's sortedness property to efficiently look for an item in the array. The reason why a lot of emphasis is placed on binary search is because it's an easy-ish way to understand how performing a task using different algorithms has an impact on the efficiency of completing the task. In computer science, a lot of emphasis is placed on the most efficient way to do something, and binary search vs linear search is simply a really good introductory example. It serves as a foundation for more complex algorithms and data structures.
Hope this can convince you that the triviality of the problem serves a purpose and that binary search is not useless!
@@KylieYYing @Kylie Ying Thanks for this amazing explanation! This type of answers really makes me wanna dive deeper into learning algorithms and cs stuffs. I'll hopefully be a SE freshman soon, and would love to watch other cs stuffs from your channel.
@@KylieYYing wow, some answer, that was! I understand its usefulness, just didnt quite see it with sorted dsta. You have indeed convinced me. Thanks for that explanation... i hope it didnt take longer than your video took - I'd feel so guilty. ❤
I'm here to learn how to love