Famous Computer Science Algorithms - Full Course

Key Takeaways

Welcome to this course on famous computer science algorithms. In this video, I'll explain six key types of algorithms that you need to know and that will come up in any computer science course or potentially technical interviews. Now, the algorithms are as follows and can be navigated to from the video player below. So, we have recursion, linear/binary search, sorting algorithms, path finding, minimum spanning tree, and dynamic programming. Now, this is meant to be a practical walkthrough where I focus only on the parts of the algorithms you actually need to know and that you'll use on a day-to-day basis. I don't dive extremely deep and I don't go into a ton of unnecessary theory. Now, in fact, the videos that you're going to see here used to be a part of one of my premium programming courses that I since made free for everyone on YouTube. Now, with that in mind, if you are someone who's learning this topic to land a software engineering role or to pass technical interviews, then make sure you sign up for my free newsletter, which I'll link below. Every week, I break down a ton of practical tips on career growth, interview prep, and the tech skills that actually matter in this job market with no fluff and just the stuff that actually moves the needle. Takes just a few seconds to sign up. Again, it is completely free. And if you do so, I'll send you over my free guide on how to make money from coding. because believe it or not, you don't just need a job to do this. Anyways, with that said, let's dive in and let's learn about famous algorithms. So, in this first video, we're going to talk about recursion. Now, recursion is again a strategy that you can use to solve a problem. So, you can write a recursive algorithm. So, the goal here is not just to have you memorize the algorithms I show you, but to teach you how recursion works and how you can apply this to any arbitrary problem that you might face. Really, the whole point of this section is to introduce you to all of these different strategies so that you can have them in your tool belt when you move on to become a more experienced developer and you need to actually write some more complicated code that may involve some of these strategies or some of these algorithms. With that said, let's begin here and talk about recursion. Well, what is recursion? Well, recursion is really fairly straightforward. It means we have some kind of function and within the body of that function, we call the function again. That is the most basic example of recursion. So I have some function fn okay and then inside the function I call it. That means we have a recursive call that's calling the same function. Now whenever we design recursive algorithms we need to come up with two things. The first thing we need to do is come up with the base case or cases and then the recursive case or cases. Okay, excuse my messy handwriting here. Hopefully you guys get the idea. So a base case is a situation in which we know what the answer to this case is. And a recursive case means we are actually going to make a recursive call to this function. Now in simple recursive algorithms, we have maybe one or two base cases and one recursive case. But in more complicated algorithms, we can have multiple base cases and multiple recursive cases. Now when we are defining essentially the recursion that needs to occur, we need to know both of these things and we need to define what both of the cases are. Now I know this is a little bit abstract. So the best way I can show this to you is with an example. So we saw in some of the previous videos that we had a Fibonacci sequence. As a quick refresher here, the Fibonacci sequence is 1 1 2 3 5 8 13 21 etc. where the value of one term is equal to the value of the two previous terms. Now this is a great example of where you can utilize recursion because what we can do is break this problem into a series of subpros and if we can solve those subpros then we can solve the entire problem as a whole. Typically when we write a recursive algorithm what we're doing is something known as dividing and conquering. We're taking what is typically a fairly large problem, a difficult thing to solve, like determining the nth Fibonacci term and saying, "Okay, well, I don't know how to determine the nth, but I know how to determine the nth minus one, or I know how to determine the first and the second." So, how can I use some of the subpros or solutions to those subpros to solve the main problem? That's really the idea behind recursion. And in a few minutes, I'll show you a few examples in code, and this will start to make a bit more sense. Okay? Okay, but when we're talking about our Fibonacci numbers here, what we need to do if we want to solve this recursively is determine first of all the base case and then the recursive cases. Now again the base cases are cases in which we know the answer to the problem. Now you can define many different base cases for Fibonacci but in this case the two base cases that we need are these right here. So this is the first term and the second term. So what we'll say is the following f at one where f is our function for the recursion is equal to one and f at two is equal to two and then we can sum these up and say that these are the base cases. So now we have two base cases which means if we reach this case we know what the answer is and sorry this is not equal to two this is equal to one my apology. So f of one is equal to one and f of2 is equal to one. These are the two base cases where we know the answer to the problem and there's no more computations that we need to perform. Now that we know what these base cases are, we need to define the recursive case. Now, there can be more than one recursive case. However, in our case, they'll just be one. So, I'm just going to put R standing for the recursive case. And this is equal to the following. F of N is equal to F of N minus one plus F of N minus 2. So what we're doing here is writing something based on the parameter that we have which is n that will recursively be able to solve the problem for us. So we've already walked through the entire call stack. I'm not going to repeat everything we've done in the previous videos. But the idea is if we're trying to look for say this term right here, well if we can calculate the term before and the second term before, so the previous term and I guess the term before that, then we're able to solve this problem. And if I don't know what the result of this term is, then I would recursively again calculate the result by taking the two previous values. So this is a great example of simple recursion where we have one recursive case which is f of n is equal to f of n -1 plus f of n minus2 and then we have our base cases where f of 1 is equal to 1 and f of 2 is equal to 1. And so long as we will eventually reach these base cases, then we're going to be able to solve this problem recursively because we know the answer to a very very small problem. And then we take those answers and we move up slowly to answer the larger problem as a whole. Hopefully this is making a tiny bit of sense. I don't want to get too theoretical with you, but this is the notation that you would write if you were writing down kind of the theory for recursion. You define the base case or base cases. There can be multiple depending on the problem. And then you define the recursive cases. In this case, we have one recursive case, but we could have another. For example, maybe we have a recursive case when n is even and then a different recursive case when n is odd. Many different things you can do here to solve an algorithm recursively. Or not to solve, but to create a recursive algorithm. Again, this is kind of known as divide and conquer. I'm saying, okay, to solve this problem, I need to solve these two sub problems. To solve these two sub problems, I solve these two sub problems. So on and so forth. Okay, so that's it for the theory here. Now I actually want to go to the computer and show you some code to make this more clear. We'll begin here by writing a function. We'll call this fib for Fibonacci and we'll take in one parameter n. Now remember we need to start by defining our base cases. So I'm going to say if n is less than or equal to two then return one. Okay, so this means if we're passing one or two also if we pass zero we're not going to be doing that but if for some reason we did we would just return one. Okay, so this is our base case and that handles those two base cases I discussed where we have n= 1 or n= 2 and that means we are returning the value one. Okay, so we can kind of comment this and say this is the base case. Then we have our recursive case. Now the recursive case is simply the Fibonacci of n minus one plus the Fibonacci of n minus2. Very straightforward, probably the most basic example of recursion we can use. All we're saying is that if we are not in our base case, then we need to go to our recursive case. And the recursive case means that we're taking the previous term plus the second previous term and adding those together. So let's have a quick look at this. I'm going to say console.log. Let's go up here and say const result is equal to the Fibonacci of something like five. And then we will log our result. So I'll say node program.js and we get five. That's correct. If I do six here, we get eight. 7 we get 13. Okay, so this is working correctly and giving us the correct Fibonacci terms. Now let's have a look at what happens if we try to call this on a very large number or a very large term like 70. If I run this, notice that this is actually going to take an extremely long amount of time. In fact, there may not even be enough time for me to execute all of this code because the time complexity of this algorithm is so poor. Remember the time complexity of this is bigo of 2 to the exponent n which means it's going to take 2 to the^ of 70 which is an exponentially massive number relative time to run. So this is still running like it still hasn't finished yet because of how poor the time complexity is. So I want to show you there's actually a way that we can significantly increase the speed of this type of algorithm. It actually involves not writing this recursively. So since we're doing this recursively, what happens is we have two different base cases that we need to solve for every single case. And then we're going to recursively keep adding to that as we increase the value of n. So you can see at small values of n, it's not really a big deal. But as n gets to like 20, 30, 40, 50, 60, 70, etc., it becomes infeasible for for us to actually run this algorithm, which is one of the main reasons why we even talked about time complexity. because if you have a time complexity like this, well, this function is pretty much useless when it comes to large terms of n. So, let's see how we can rewrite this. All right, so what we're going to do here is write a new function and we're going to call this fib memoized. Now, what this is going to take in is n and a calculated object that has our base cases inside of it. Now, let me just quickly explain something. When we're looking at this Fibonacci function right here, the reason it's so inefficient is because we're constantly recalculating values that we already have calculated in the past. For example, if we look at calling Fibonacci with the value five, well, the first call that we need to make is to Fibonacci of four plus Fibonacci of three. But then Fibonacci of four, right? If we go down here, this requires the call to Fibonacci of 3 plus Fibonacci of two. Three requires the call of 2 + 1. Now we can continue with this and you'll see that every single time we increase the number uh the term n here that we're calculating we're constantly doing more calculations repeated calculations of things that we've already calculated. So already here we've calculated three twice two twice we're going to calculate one two and a bunch of these other values multiple times. Now if we only needed to calculate them one time that would drastically reduce our time complexity. In fact, if I only needed to calculate each Fibonacci term one time, I would be able to run my algorithm in the big O of N time, which is what we can actually do here when we go and add something known as memoization. So, memoization is essentially a cache. Now, a cache is a place where we're going to store values that we've already computed. Meaning, we only need to compute each Fibonacci term one time. If we do that, then that allows us to actually run this algorithm much faster and then simply look at the values we've already computed rather than recomputing them each additional time. So let me show you how we write that code. So let's begin by first checking if the key n is in the calculated object. If it is, then we can simply return calculated at property or key n, which will then give us the value. So right now I've just written in the value 1 and two which are base cases inside of this calculated object. Next what we'll do if we haven't already computed this value is we'll compute it. So we'll say if or not if sorry we'll say const result is equal to the fib memoized of n minus one. And we're going to pass this calculated object again plus the fib memoized of n minus2 and again this calculated object. Then we're going to say calculated at n is equal to the result and then we'll simply return the result. Okay. So the only addition we've made here is that now we're reading from our memoization cache and we are storing whatever value we make inside of the cache before we return it. So we calculate the result stored inside of calculated and then return the result. So now if I call my fib memoized with 70 and we say con result and we console.log log the results and I go here and run this code, you'll see that we actually compute this value almost instantly. We've gone from a big O of 2 to the exponent end time to bigo of end time by making this very simple change to our recursion. So you don't always need to do this, but in this situation, it's helpful because since we have two recursive function calls that we're making, and these end up going down different stacks that repeatedly call the same values or compute the same values, if we store those, that drastically increases the time complexity of our algorithm. I won't go too much further into that, but I'll now show you one last way that we can write this Fibonacci algorithm iteratively that's going to actually solve this um even a little bit better. Now, it's going to be the same time complexity, but it's going to have a reduced space complexity. So, when we use recursion here, one thing that we haven't really talked about is the space complexity. Now, the space complexity is essentially how much space is taken up in your computer's memory. I don't want to get too much into it, but when we're looking at something like having this memoization cache, that means that we're going to have big O, and I should make this in a comment, but that's fine, of n space being used for this algorithm. The reason for that is we're going to be storing at most n elements inside of this cache which means we'll be taking up bigo of n space. Right? So the time complexity and space complexity work pretty much the exact same way. But with space we're just concerned about the maximum number of elements or space that we would be taking up. So in this situation it's bigo of n space because we are storing all of the different results that we've already calculated. Now there is actually a way to reduce the space to constant space and the way we can do that is with this last algorithm. So function fib it which stands for iteratively. I'm going to take in n here and I actually don't need to use recursion to solve this Fibonacci problem. Obviously the whole point of this video is to show you recursion but I'll just show you the iterative approach because it's a very famous algorithm. Okay. So inside of here what we're going to do is we're just going to write if n is less than or equal to two then return one. Okay just to kind of handle the base case here so that we don't need to handle that in the next lines that I'm going to write. Now what I'll do is I'll define two variables last equal to one and second last equal to one as well. Now this is going to be for term two and this is for term one. Okay. So the idea here is that I don't actually need to store every single result that I've calculated. All I need to be able to calculate the nth Fibonacci term is the nth minus1 and the nth minus2 term. So what I can do is calculate those starting from the very first term, move my way up while always keeping track of the previous two terms and then I will have solved the problem. So let me show you what I mean here. But again, what I'm doing is I'm now kind of mitigating this recursion and saying, okay, if I just keep track of the last and the second last term, then once I get to n, I know what the value is. I can just add those two terms and return it. So I'm going to say four let i equal 2 i is less than n and i ++. Now I'm saying i equal to two because in this situation we've already said that i is going to be greater than or equal to two because if it wasn't we would have returned here and then we've defined that the last and the second last term are these two values. Now what I need to do is just update the last and the second last term. Well first of all the last and the second last term are going to be kind of relative to each other. So the second last term now as I move through this for loop is going to be equal to the last term and the last term is going to be equal to itself plus the second last term because what I'm doing every time I iterate through this for loop is I'm essentially increasing n where n is the Fibonacci term that I'm calculating. So I start by calculating the third term then the fourth then the fifth then the sixth so on and so forth. And to do that I use these two variables. So what I'm going to do is say const temp temp is equal to last. I just need to store what the current value of this last term is. Then I'm going to update the value of the last term. So I'm going to say last is equal to last plus second last. And then I'm going to say second last is equal to whatever last was equal to before that. Okay, I know this is a little bit confusing, but I'm saying all right, now I want to calculate whatever the term is. So to calculate this term, I take whatever the previous term was and I add whatever the second previous term was. Now though, I'm going to store that in last cuz now that's the last term that I calculated. And then the second last term will just be equal to whatever this was equal to before I did this addition. So now all I need to do down here is simply return whatever the last term is cuz that will be the nth term once I get through this entire for loop. I don't want to explain it too in depth but this is the iterative approach. And now if we do something like const result is equal to fib iter at something like 70 and then we console.log log the result. If I go here and run this, you can see that we get the same result that we got when we called fib memoized. Now, this is going to run in big of end time because we have a for loop that's running end times. However, we're going to use constant space because we no longer have this memoized cache or object that we need to be reading from. Okay, so that is the Fibonacci sequence. All three of these algorithms are extremely famous and that's why I wanted to show them all to you in this video. Now let's just quickly comment the time complexity. So this is big O of N time and big O of N space. Okay. And then this will be big O of N time and big O of one or constant space. Now I'm not going to go through the space complexity of this one, but there is actually a space complexity that is larger than constant time. Okay, so we're not going to look at that right now because I don't want to get too far into the weeds there. Let's move on to the next algorithm. Okay, so for this algorithm, what I want to do is show you how we traverse a binary tree. So let's make a comment here and just say binary tree traversal. And let's go up here. We'll just do a kind of a header comment and say this is fib. Now I'm going to make this code available to download afterwards. Hence why I'm kind of mark it up marking it up for you. Sorry. So first of all, for our binary tree traversal, I want to show you how we recursively do the in order, pre-order, and post-order traversal. In order to do that though, we need a binary tree. So I'm just going to bring one in here. We have a node object, okay, that has a value, left and right property. We have a constructor for creating that node. Now, what I want to do is initialize a binary tree using this node object. So, I'm going to paste this in here. And what this does creates a binary tree that looks like this. Okay, so we have our head node node 2 3 4 5 6 7 8 9 10. Notice I'm kind of uh defining them in reverse order because I'm using one of the previous nodes that I defined inside of one of these nodes constructor to set it to be the left or right child. So in this case my head node which is one has a left child of two and a right child of three. So that's what I've defined right here. Okay, you can read through that we're using this node class. All right, so now that we have a binary tree that is represented with our head, we can write an in order, pre-order and post-order traversal. So to do this we'll write a function. We'll call this function in order and we'll take in some kind of node. Now remember the in order traversal goes left visits the node and then goes right. So first thing we're going to check is if the node is equal to null. If it is we'll simply return because there's nothing we need to do. Otherwise we'll call in order on the node. And then we will say console.log the node. And then we will say in order on the node write and that's it actually we just wrote the in order traversal for a binary tree. So we're just breaking this problem down into subpros and then solving it recursively. So the base case is if the node is equal to null. If that's the case we don't need to do anything right we've reached kind of the end of that recursive call stack. So we simply return. Now the recursive cases are these where we visit the left and we visit the right node. So visit the left, print out the value, and then visit the right. That's the in order. Now let's copy this and do the pre-order, which is going to be extremely simple. So we're just going to change these to say pre. And now I'm just going to print my node value before I visit the left and the right. There you go. We've just implemented the pre-order. And now if you want to do the post order, we'll write post post. And now we just put these before we print the value. Okay, there you go. We now have the in order, pre-order, and post order all working recursively. So, let's try them out. Rather than me writing out all of these prints, I'm just going to paste them here. So, console.log in order, then we do the in order, then we do the pre-order, then we do the post order. Let's give this a quick demo. Node program.js. Let me just make sure I'm not calling my Fibonacci. I'm not. Okay, that's good. Let's make this full screen here. And you can see that we get the in order traversal of the tree, the pre-order, and then the post order. Now, trust me, these are valid. I'm not going to go through and explain why these are the case. We've already looked at how we do the pre uh post and in order traversal in that binary trees video. All right, so moving on. The last thing I'm going to show you is a more abstract algorithm which allows us to reverse a string using recursion. Now obviously reversing a string can be done without recursion but I just want to show you another way that we can write a recursive algorithm. So let's say we have a string. So const str is equal to something like Tim is great. Well how do I reverse this? Well to reverse this I simply write all of the characters in the string starting from the end back to the beginning. Right? So I take the exclamation point the t the e or sorry the a etc. And I just write them backwards. little bit easier said than done, but that's the premise. Now, in JavaScript, we have some built-in ways to reverse this string. Kind of some shortcuts to do this. We can also just write a for loop where we just loop through the string backwards and write all the characters into a new string forwards. But we can also do this recursively. So, let me write the function then we can explain it. Let me just write above the string here. So, we're going to say function reverse string and we're going to take in a string and we're going to say new string is equal to an array. Now what I'm going to do is append all of the new characters for my new reverse string into this array and then I'm going to join those characters together at the end uh to create the new string. The reason for that is that it's a big of one time complexity operation for me to insert an element into an array. Whereas if I have a string and I try to add something like one to this string, what actually happens is I need to rewrite the entire string which is a big O of K time operation where K is the length of the string. So if I use a string and I concatenate to a string, this takes me whatever the length of the string is, time, length of the longest string or length of the two strings combined, whatever you want to write out here. Regardless, it's going to take me that length because again, I need to rewrite the string because this is an immutable object. Whereas since the array is mutable, I can simply write into that array in constant time by pushing elements to the end rather than having to remake the entire array every single time. So that's kind of a little thing to remember here. When you're concatenating to a string, that's a big OO of N or big O of K depending on how you want to say it operation. Whereas when you are appending to an array or pushing into the array, that's a constant time operation. Okay. So first thing I'm going to check here is my base case. So I'm going to say if the string.length is equal to zero, then I'm simply going to return. So if I have no string to reverse, well then I don't need to reverse it. So I can return. Now what I'm going to do inside of this recursion here is I'm essentially going to reverse the string one character at a time. So the reversal of a string can actually be written like this. String or the reverse string is equal to reverse string dot slice 1 plus whatever the string at the first index is. Now, I know this seems a little bit strange, but essentially what we can do here is reverse the string one character at a time. So, we'll say that if we're looking at this string right here, the reversal of this string is equal to the reversal of the rest of the string plus the first character. Okay? So, that means the first character will be at the very end. So again, we're kind of writing it like this where we say that this so the reverse of this plus t is the reversal of this entire string. That then means if we're looking now at this instance here, the reversal of this string is equal to the reversal of this plus i. And you can continue and break this down until eventually you get to a string that has one character or no characters. Right? So the reversal of a string that is zero characters is zero. The reversal of a string is one of one character is just equal to itself. And then again you can kind of repeat this process and break it down until you get to the smallest possible case which is where the string has no length. I know this seems abstract. Let me just write this out and then we can kind of walk through it step by step. Okay. So we have the base case which is the instance where the string length is equal to zero. Now what we're going to do is we're going to grab the first character from the string and we're going to store that in a variable. Then we're going to say reverse string and we're going to reverse the string slice which will simply remove the first character from this string. So reversing all of the characters except the first. And then we'll pass inside of here the new string array. Then what we'll do is we'll say new string.post a push and then the character. So what this means is we're going to reverse the entire string and once we've reversed the entire string then we're going to push this new character to the end of it. So again the reversal of any given string is equal to the reversal of the rest of the string plus the first character in that string which takes the first character and moves it to the end of the string. Now I'll print this out so you can see what's happening but I'm going to come down here now and say if the string.length length is equal to the new string.length, then return new strin. And we'll just put an empty string inside of here. Now, what this does is create a string out of an array of characters, which is what it will do. And I'm only doing this if we're in the case where the length of the string that we have here that was passed in is equal to the length of this new string array. Okay, so let's just make sure this works. I'm going to say const result is equal to reverse string str and then I'm going to say console.log result. Okay, going to come here and print this out. And notice that I get my reversed string. Now we just comment these out here cuz I don't need that right now. Okay, let's run that again. And you see we get the reversed string. Okay, so now let's print this one step at a time. What I'll do is I'll say print. And actually, what should we print here? I'm wondering the order we should do this in. So, actually, I'm going to go here and I'm going to say console.log. And we're just going to print the string and then the new string uh before we push this character in. And actually, no, we'll do this after in this case right here. Okay. So, let's have a look here and run this program. Now, I know we get quite a bit of output here, but you can see that the very first string that we end up actually adding into this new string array is the exclamation point. Now, the reason that's the first string is because that's the first instance where this function call just returned. It didn't go into another kind of stack or another uh recursive call. So, as soon as we hit the exclamation point, when we call reverse string, that simply gives us nothing, right? We just return here. So then we take whatever character we had which is the exclamation point and we push that into new string. Then we print that out. We check this. We say okay we don't need to return anything. And then we continue the process which means then we're going to go back to whatever called the call that just added the exclamation point into this string. So now we have t exclamation point right. So what we do is we have the exclamation point which is already inside of new string and then we append the t. We push that in because we had to first reverse this string before we could add this character to the end of the reverse string. Then we come to this where we have a t exclamation point. Now we have exclamation point t and then we add a. So after we reversed this substring or sorry this substring t and exclamation point, we added this character to the end. And you can repeat this process and see that we continually reverse all of these substrings one character at a time until we get to the point where we're at the very last substring and we're adding t. Okay. Now, I don't know why it skipped some of the outputs. I think it just didn't all fit in the terminal. Okay. So, there you go. You can see now the rest of the output is here. Regardless, that's kind of how this works. I know that's a little bit abstract. I didn't go into a ton of depth here. I don't want to spend like 30 minutes per example explaining this. I just wanted to show you that we can be very creative here when we're doing something like recursion and we can come up with ways to recursively solve problems that we didn't think we could solve. The main premise again behind recursion is we're breaking the problem down into smaller problems and once we do that we're then able to solve it recursively. So if I was writing the recursive notation for this, I would say that the reverse of some string is equal to the reverse of the string slice at one. Okay? Plus and then whatever this string at index zero is. Now I know that we already wrote that out, but this is the recursive case. Whereas the base case is when string.length the length is equal to zero, then we just return an empty string or we return nothing. Okay, that's the base case. All right, so with that said, I think I'm actually going to wrap up the video here. This was all that I wanted to show you. Just a few different recursive algorithms to give you a sense of how we would go about using recursion and actually implementing this in code. So, first of all, what is a searching algorithm? Well, searching algorithm is just an algorithm that searches for a specific value. It can be searching to see if something exists. We're searching to find the position of that element. So if we have some array here and we have some kind of random values here inside of the array, we know that if we want to locate a value inside of this array or see if it's present, that's going to take us big O of N or linear time. The reason for that is if I wanted to see if say element seven exists inside of this array, I would need to look through at most every single element in the array to a say that it doesn't exist or b find the location where it does exist. Now, in some instances, it could be the first element. In that case, we'd get lucky. This would be very fast. But if it was the last element, we'd have to look through all of them before we find that. So, just kind of a quick recap here. This is a linear search. We've done this all the time. We know this time complexity and I just wanted to refresh you on that. So now imagine though that our array is structured a little bit differently. For example, maybe we actually have a sorted array. Well, if we have a sorted array, then that actually means that we can find elements a lot faster. The reason for that is now the positions inside of these arrays for the elements are not arbitrary. It's actually based on some kind of ordering. So let's say I wanted to find the element three, but I know that my array is sorted. Well, how can I go about locating three? Now I no longer need to search through every individual element. What I can actually do is use an extremely efficient and popular algorithm known as binary search. Now, the reason it's called binary search is because you are essentially splitting the problem in two or having the size of the array that you need to search through every single time you do a search operation. The reason for that is that since we know this is sorted, I can either look to the left or to the right of any individual element and I can narrow down my search quite quickly. Let me show you what I mean here. So, let's say I'm looking for three. Well, what I can start by doing is picking the element that exists in the middle of my array. I can say, okay, well, I'm going to look directly in the middle of my array and I'm going to see what the value of this element is. Now, in this case, it's seven. So, since it's seven, I take my value three and I compare it to seven. And I first of all say, are these equivalent? If they are, I've just found the index where three exists and I've kind of completed my search. If they're not, that means that any elements to the right of seven are not going to be three, right? Because all these elements are greater than seven. So the only remaining elements I need to look through are these over here in the kind of left half of the array. So now I can repeat the process and I can pick the middle element again. Let's say I pick the element two. Now I know that's not the ele middle element. I'm just picking it here so that we can kind of continue with this example. So let's say I pick two now. Okay, which is relatively in the middle of these elements. Well, now what I can do is I can look again to the left and to the right of two. So at this point, we've kind of narrowed the array down to this. And really, we've narrowed it down to this cuz we know that seven is not the element. So now I'm looking at two and I'm saying, okay, well, I'm looking for three. Is three less than or greater than than two? Well, it's greater than two, which means I don't need to look at any of this part of the array because anything to the left of two is going to be less than that. and will my element's greater. So now that narrows me down to this subarray right here of three and four. Now I can pick either element. Let's say I pick three. Well, I've now found my element. Let's say I pick four. Well, I know it's not four. And then the only remaining element would be three, which is right here. Hopefully you kind of get the idea here. But what we're doing is we're essentially narrowing the search by having it every single time. So if we do another example here where we're searching for element say 14, we'll repeat the process. Look at the middle element. Is it greater than or less than? Well, it's greater than. That means we no longer need to look through any of these elements. We just need to look to the right of seven. And sorry, I kind of deleted too many here. So, let's go up to that. Okay. So, now we're only looking in this. Now, again, pick the middle element. Okay. Is it less than or greater than? Greater than. So, we delete all of this. And actually, now we're just looking here. Obviously, the middle element of an array with one element is simply that element. So, it is 14. And we have found that. Now, we could continue here. And if we had an element like 16, well, what would happen is when we get to this point, we'd see that there's no more elements. And then that would mean that 16 does not exist inside of this array. So, that is the binary search. Okay? And the binary search is extremely efficient because again, we're having the problem every single time. Now you can implement a binary search recursively which is actually what we'll end up doing. Now the time complexity of this search operation in the binary search is log base 2 of n where n is the number of elements inside of the sorted array. Again this only works when the array is sorted because we know one of the properties of the array which is every element to the left is less than every element to the right is greater than or equal to. That allows us to do this very efficient search. So I have this massive array. Well, I start by splitting the array in half. So again, let's just do an example here. Let's say we have an array of a,000 elements. So we start by looking at the entire thousand elements. Then we split this in half and we're only looking at 500. Then 250, then 125. And then this is what 62.5. Okay. And then you get down here to what's this going to be? Something like 31.75, etc. Okay. You just keep doing the math and keep having having having and you end up getting time complexity of log base 2 of n. So very quickly you can search through a very very large structure if that structure is sorted. Now one thing to keep in mind is that if we want to sort something that's going to be a n log base 2 of n time complexity operation. Okay. So sometimes it may actually be in your favor to first sort some type of structure then look through the sorted structure with a log base 2 of end time complexity operation. Not always. Sometimes it's actually better just to do some type of linear search. But if you need to do repeated linear searches and it's okay for you to sort the array first, you can save yourself a bit of time by first sorting the array. So anyways, that was the algorithm I wanted to explain on the whiteboard here just so you understand how that works. That is the binary search where you constantly split the array in half and search through one of those halves giving you that log base 2 of n time complexity. With that said, let's now go over to the computer. I'm going to show you how to implement the binary search and then we're going to look at a depth first search and a breadth first search and just see their code implementation. All right, so I'm on the computer here and we're now going to implement the binary search algorithm in JavaScript. Now we're going to do this recursively and essentially the recursive case is that we're having the array, right? So we're just looking through one half at a time. That's how we're doing this recursively. And then the base case will be the situation where the array is no longer large enough for us to search. So there's no elements inside of the array or there's only one element. In that case, we can determine if the element exists there or not. Okay, you'll see what I mean as we start writing. So I'm going to say function, let's just call this search. And what we need to take inside of here is some kind of array, some kind of target, and then a start and end index to look at inside of the array. So rather than creating new versions of this array that are slices of the array which will take us whatever the size of the slice time is, we're simply going to look at a start and end index inside of the array. Okay, hopefully this makes a bit of sense, but that will also allow us to access whatever the index inside of this array is for the element that we find. You'll see what I mean as we go through this, but rather than recreating arrays, we're just looking through a section of the array using this start and end index. Okay, so what do we need to do here? Well, we need to say first of all our base case, if the start is greater than the end, then we're going to return false indicating that we did not find the element that we're looking for, which is the target. The reason this is the base case is because we'll be switching both the start and the end as we recursively call this function. If the start eventually becomes greater than the end, that means we've exhausted the search and looked through all of the different elements. Next, what we need to do is determine what the middle element is. So, we're going to say const middle is equal to, and this is going to be math.f floor and then we're going to take the start index plus the end index and divide that by two. So just as a quick illustration here, let's say we have our sorted array. Okay, we have index zero there and we have index 7 here. So when we first start searching through this array, we take 0 + 7, we divide that by two, that gives us 3.5. We then floor that, that gives us index 3, which is 1 2 3. Okay, so now we have the middle of three. Now let's say we start searching on the right side of the array. Well, now we have three and then index 7, right? So what I do, this is my start, this is my end. So I take these, add them together, that's 10. Divide them by two, that's five. So now that tells me the middle element is at index five. Okay, so that's why we're doing this to determine the middle. We take the start plus the end, divide by two, and that gives us the middle or the uh yeah, just the middle value in between those two numbers. Just kind of some simple math there. Okay. So now we're going to check if whatever the array at the middle index value is and we're going to see if this is equal to our target. So we're going to say if array at middle is equal to target then return true indicating that we found the target. We also could return the index which is simply middle uh which is where this element exists. Okay, we might not care about that. We might care about that. Uh it doesn't really matter for this example. For right now, we're just going to return true. And this will say found the element. All right. Now, let's continue. So, if we didn't find the element at the middle index, then we need to see if we have to look on the left side of the array or the right side of the array. So, we're going to say if array at middle is greater than the target, then what that means is that we need to look at the left side of the array. So we could write this the other way around but essentially this is saying if the target is less than the uh middle element in the array then we need to look left. So how do we do that? Well we return the search with the array the target the start and the middle but this time we're going to say middle minus one because we've already searched what the middle element is. Okay. So we're now recalling this and all we need to do is change what the end is equal to to be the middle index minus one because we've already looked at the middle. Otherwise we can simply return the search add array target. Then this is going to be middle + one and then the end. So now we're changing the start to be equal to the middle plus one rather than the end because we're looking on the right side of the array. That's it. That finishes our binary search. So now let's see how this works. All right, so we need a sorted array. So we're going to say con ar is equal to 1 2 3 4 5 6 7 8 9 10 11 12 13 14. Okay, let's pick a target. We'll say const target equals I don't know, let's go with 11. And then we are going to search. So we're going to say const result. If we spell const correctly is equal to search and we're going to search the array okay for the target and we're going to start at zero and our end element is going to be the array.length minus one uh because that is the last index inside of our array. Perfect. Then we can console.log the result and this should tell us if the element exists. Let's go ahead and run this. And notice that we get true. Now, let's put an element that doesn't exist, something like 15. And when I run this, we get false. Sweet. Now, what I want to do is just print out the number of operations and actually the array that we're looking through as we're doing this, just so that we get kind of some sense of what's going on here. So, what I'm going to do is at the beginning of this function, I'm just going to print out the array from the start to the end index. You can see how we kind of narrow down these values. So, not print, but console.log log. Now, this is going to essentially ruin the time complexity, but that's fine. I just want to show you what's going on here. I'm going to say start and then end. Uh, and this is actually going to be end + one. Okay, now let's go here and print this out. And actually, let me just make this a bit larger. You can see the arrays that we look through. So, we look through this array, then we look through this subarray, which is kind of from the right side here, and then we look again to the right, and then again to the right. We don't find it. So we have false. Now if we switch this to something like two, an element that does exist, and we print this out, you can see we search through the entire array. We search through half the array. Search through another kind of half here. And then we find the element two. There you go. Those are all the operations that are being performed. All right. So that is our binary search. Now let's remove this. All right. So moving on, we're going to get into depth first search and breadth for search. And what I'm going to show you is actually how we would navigate a maze using both of these algorithms. All right. So, what I'm going to do here is just paste in a maze. I actually got chat GBT to generate this for us. And what I'm going to do is show you how the depth for search and breath for search algorithm works when it comes to traversing this maze. Now, I'm not going to show you something like a shortest path finding algorithm. Uh, that's a little bit more complicated. All I'm going to do is essentially run first of all the depth first search on this maze which will go through and traverse a bunch of the different positions until it finds this X. The X is going to be our finish. These pounds are a wall and these spaces are going to be a valid path that we can go through. So we just want to see kind of where the depth for search is going to move and how it's going to locate this X versus how the breadth for search is going to locate. Again, this is not a super practical example, but I just want to show you writing uh these kind of algorithms here when it comes to traversing something like a maze. So, I'm going to make a function here called DFS, which stands for depth for search. And I'm going to take in an array. Now, what I need to do here first of all is I need to make a set called visited, which is going to store all of the elements that I've currently looked at in the depth first search. Now, the reason I need this is because unlike binary trees, we're actually going to have circular references here to the neighbors of different positions. To walk you through the basics of how the algorithm will work, I'm going to look at some position. In this case, 0 0, right? The position is going to be kind of like x0 y 0. That's how I'm going to represent the different positions in my array. So, we have all of the different y values, which are rows or individual arrays, and all of the x values, which are the column positions. So, I start at 0 0. I look at this position. I see that it's an empty string or that it's a space. So what that means is that this is a valid position to traverse and I now need to look at all of its neighbors. So the left, up, right, and down element and see if I can move to any of those. In this case, the only valid neighbor to move to