In this episode we covered how binary search works and when we should consider it in practice. You can find links for further reading below:
We just started looking at this. The elements in a particular way we just follow the binary search algorithm and we optimized searching functionality. Dramatically another example is when I was working on the learning thank platform Ryan Dot Com. Their use case was slightly more complicated. I was working on recording where you were able to record the screen of a virtual machine that is running inside of the browser and on top of that. We're also recording the different user events. For instance one user moving their cursor cursor we were recording wear the cursor is on the screen we are also recording which keys the user was pressing a while interacting with the virtual machine. So this way we had different events these events were stored in an array and for each individual event. We had the type of event what actually happens and a time stamp associated with it. Since we're recording these events sequentially. They were ordered ordered based on the time stamp. Now we had two streams we had the video stream of the virtual machine and we also have this events three of course yes we also had some extreme but it is not interesting for this particular example that will be looking at so once the user recourse this. We were saving this somewhere in Google cloud or aid that wes. It doesn't really matter once so we'll start looking at the media they were. You're supposed to see the video and also and also see some cassation of of the of the events for example when the recording was yes Capturing interaction of the author of the recording with a particular element with their mouths we were visualizing leising demolished events in some special way. Because because we wanted to make them be more noticeable and more intuitive for actual consumer of the recording so once the consumer of the recording navigates to a particular time in the video. We wanted to find out which is the a particular mouse or keyboard events ASSOC- associated with this time stamp and now imagine a long recording a long recording. Kim consist list of maybe hundreds or even thousands of events or even menial servants. Now imagine you as a consumer of the video you navigates to particular Ornstein. Veto you click there and well if we're using If we were using a exhaustive search or leaner leaner search. We had to start looking at the individual events one by one. We're going to start from the beginning in to find out whether this is the closest event onto the time stamp that you navigated to Ashrat. We had to navigate to the second element third element and so on and so forth until we eventually reach the closest closest events to the time that you went to now in the large video. This could be terrible in John Scripts in general. We we have about when running in the browser. We have about sixty seconds to perform an operation to perform computation because otherwise alternatively the browser is going to start dropping frames and drop the user experience in general making. We're going to make it worse from sixty percents. We're going to directly drop to thirty frames per seconds or less now if you have to perform an exhaustive for dinner searching on top of one hundred million items we'll have to perform one hundred million comparisons in the worst case because the item that we're looking at the item that we're actually looking for. It could be somewhere in the end of this list however her if we were using binary search we can drop the number of comparisons to log in which is only twenty seven comparisons imagine engine. We're dropping from a hundred million comparisons to twenty seven. This is an extremely powerful algorithm. So how does it work in research. Actually it has a simple idea we can think about it as looking for full number or dress address book. We know that the names in the address book there are ordered by the names of the people inside back within that we have their addresses. So if you're looking for a particular person we can. I look at the middle of the address book and depending on whether and depending on whether the names in the middle are Bir likely graphically or smaller again.
Lexi Lexi graphically compared to the name that we are looking for. We can decide whether we want to start doing the same in the first half of the address book doc or in the second half for example if we're looking for a person which WHO's name starts with E. I we're going to take a look at the middle. We're going to to figure out that well probably. That's not the place where we're looking at because all the names the middle are with a letter which is much bigger than e graphic traffic. So we're going to ignore the second half of the address book and we're going to entirely focused on the first half of the address book so we're going to look at the half exactly exactly the middle of the first half and we're going to figure out that well that's probably not the place to look for dispersal whose name star Suite E so we're going going to ignore the second half of this first half of the address book so we're going to ignore pretty much the second quarter alter and we're going to focus on the first quarter. See How on each step. We're ignoring half of the input. This is extremely powerful technique. Because you'll see drops the number of operations that were performing while searching dramatic so this is why finery search is much more efficient compared to a linear exhaustive search but how much more efficient. This is a very interesting question to ask in fact because it relates to analyzing the complexity of this algorithm by complexity I mean the runtime performance of the Algorithm. There is a very solid foundation for analyzing Complexity of particular algorithm by looking at how algorithm is going to scale over time when we increase increase the input to understand better. Let's actually look at the particular implementation of binary search so we have our rate which has n elements. We also have a particular element that we're looking for. In general we want to find whether element x exists in the IRA and what's index. So first we're going to take our array and look in the Middle Adamant we'll get to compare X.. With the element of the middle and if x equals to this element which is going to return the index of the Middle Element which is perfect. We already found the tremendous. When does we're looking for alternatively if the element of the middle is bigger compared to the elements X? We're going to completely ignore the second in half of the IRA. Because we know that all the elements in the second half of the array. They're bigger than the first settlement. Remember one of the preconditions for binary search coach was our array to be sorted as the next step. We're going to look at the first half. We're going to find the middle element in the first half and we're going to compare it with X.. If this element in the first half the middle one equals X.. Them well we found the exact no matter who looking for so. We're just returning cynics. Alternatively if it is bigger compared to x then we're going to ignore the second a quarter and we're going to focus on the first quarter now see how we represent binary search with this decision. Trie we I have the decision to figure out whether adamant equals whether x equals the Middle Element or alternatively we look at the first half or the second half the afterwards if we go to the first branch look either at the first quarter or the second quarter if we go to the second half look at the third quarter or fourth quarter this way we actually truly have a binary a balanced binary tree and finding whether our element existing there or not you just a pass from the rules of the of this three to any of the leaf notes so this is actually fascinating but the decision tree that we're going through during the execution of binary search you just another another data structure that is pretty common. boggles binary tree the height of such panels binary is look and by local I mean logarithms. With based to from end since well we're not calculating logarithms. Didi and I don't do that. While I wanNA vacation or like walking in the park let's make a very quick recap of lot walk and logarithms Based to avenge his rhythm of with base to from sixteen is going to be poor. This means that we need to take to and put it on on the power four in order to get sixteen so if we have luxury him from one hundred million with base to we need to figure out on which power we need to put to in order to get one hundred million and this is not much it is bright beautiful twenty seven now you can see how fuhr how much fewer operations in binary search were performing compared to appear linear exhaustive search.