Introduction to Binary Search (Data Structures & Algorithms #10)

Key Takeaways

hey everyone in this video i'm gonna give you a quick introduction to binary search and i'm gonna explain how it works with some samba code and at the end of the video i'm also gonna show you what i would say is a medium difficulty problem which you can solve with binary search so suppose you're given a sorted array of integers for example this one you're also given a target integer for example this one and your task here is to find the target in the array and that's a problem you can solve with binary search and let's say here that you need to write a function called search that takes these two arguments the array and the target and returns the index of the target if the target exists in the array and if it doesn't this function should return -1 instead so in this particular example your function should return 6 because the index of the target integer 11 right here is 6. and one approach you can use to solve this problem as a comparison to binary search is called linear search the idea of this approach is you start at the beginning of the array this one right here and then check if it's our target or not and if it's not our target then we go to the next element and the next element zone until we find our target or we don't find our target but find a number that's larger than the target then we can stop the search then and this approach has the time complexity of of and where n is the number of elements in the array and that's because assuming that we don't know where the target is we're going to check you know a certain number of elements in the array and on average we'll need to check about half the elements because on average you know we can assume that the target is going to be in the middle of the array and so we'll need to check n over two elements on average and that's why we have of n over two in time which is equivalent to o of n okay so as a better faster alternative to linear search let's take a look at a binary search and to see how it works we're going to use this example of a sorted array of integers ranging from minus 50 to 50. and as you can see we have 40 integers here we're also given the integer target of 20. now the first step in binary search is to say if the target exists in this array it must be between the first element this element right here and the last element this element right here another way to say the same thing would be to say our initial search region is going to be this entire array which is between the first element and the last element we can express the idea by defining two integer variables or two uh pointers which we're going to call left and right or l and r so l would be zero pointing at this element right here and r would be pointing this last element right here and in this particular example the initial value of r would be 39 because the length of the array is 40 right here okay and the next step in binary search would be to check the number that's in the middle of l and r in this particular case that's this number right here and let's say as an example that it happens to be 10. then at that point since our target is larger than 10 we'll know that the target if it exists in this array must be in this region right here so that means we can move our left pointer or l over here and then we can keep repeating the same procedure to narrow our region more and more so we can check the number in the middle of the new value of l and the current value of r that's this number right here and if that happens to be larger than target that's 30 right here then we'll know our target must be between this current value of l and this element right here so we can move r over here so just like that we can keep repeating the same procedure until the number between l and r uh the number in the middle of l and r happens to be the target at that point we can uh finish running our function because we've already found that number or uh when r comes to the left of l kind of like that and that's because at that point our search region is empty so that means that this target number doesn't exist in this array okay so we're going to put this idea into code but first before that let's think about the time complexity of this approach well with this particular example that we just saw our search region started with 40 elements and then it became about 20 and then about 10 and so on until we got down to one so the pattern we see here is we start uh with a search region of n elements which is the number of elements in the given array and then we have it and then we get the we get half of that and half of that and so on until we get one and i can write it uh slightly differently just like that so we have n and then n over two and over 2 to the power of 2 and so on until n over 2 to the power of x is roughly equal to 1 whatever this x is and now for a second let's say that n happens to be 8 that's 2 to the power 3 so this expression right here n over 2 to the power 3 becomes one so that means if n happens to be eight we'll need to check about uh three elements about three elements until our search region becomes one you might say well that's more like four elements but i'm saying the number of elements that we need to check is roughly equal to three so what i just showed you here is that when n is equal to 2 to the power 3 we'll need to check about three elements and for this algorithm to be complete so if n is uh roughly equal to 2 to the power of x then we'll need to check about x elements so basically to find the number of elements that we need to check we only need to find x such that 2 to the power of x is roughly equal to n and if you solve this for x of course you get x being roughly equal to log 2 of n and so the time complexity of this algorithm will be o of the number of elements that we need to check which is of log 2 of n and you can rewrite it as of log n for short okay so what i showed you here is not an exact mathematical proof but i hope that at least this logic is clear enough to you anyway as an example if you had 10 million elements in the given array then the number of elements that we need to check will be roughly equal to log 2 of 10 million which is 23.253 and so on which is about 24. so if you had 10 million elements in the given sortie array you need to check almost about 24 elements to find the target uh number that you're given now we're going to put our approach into actual code and to do that we're going back to our smaller example that we saw at the beginning of this video we just have eight elements in this array and we're also given the target of let's say 11 and we're trying to write our function search that takes these two arguments and by the way i'm going to show you some suit code that looks like python here but you'll be able to find the actual python and java code that i wrote for this at this url anyway the first step in this code is defining our left and right pointer left or l will be zero right here and right or r will be the array's length minus one so the array's length is 8 here and so r will be 7 and then after that we'll run a while loop saying while left is less than or equal to right or in other words while right is not to the left of l and we'll say while that condition holds we'll first need to find the mid index and that's going to be between left and right and that's going to be the average of left and right so left plus right divided by 2 and if this is not an integer you can round it down to get an integer value here and so in this particular example we'll get zero plus seven divided by two which is three point five round it down and we get three so mid will be 3 right here and the next step after that will be to say if that element r of mid happens to be the target then we've found the target so we're going to return that index mid and else if target happens to be less than that element right there so if the target happens to be for example six in this example then the right pointer will be mid minus one so the right pointer will move right there and otherwise target is greater than that element right here so that's the example we have right here target happens to be greater than seven so then left or l uh will be mid plus 1 that's right here and then we can keep repeating this while loop until we either find r of mid to be target and at that point we can return mid or left will be greater than right so for example if the target happens to be let's say 12 which doesn't exist in this array then eventually l will come to the right of r or in other words left will be greater than right so at that point we'll get out of the while loop and then we can return -1 to show that the target doesn't exist in this array okay so that's how binary search works but if you're looking for extra practice i would recommend using my business affiliates product i'll algoexpert.io which you can find at this referral link of mine and get a discount from with my discount code csdojo they have two related problems one is simply implementing binary search and the second one is called shifty binary search which i think is much more interesting so in this problem uh you're given a sorted array as well as a target and you need to find the position of the target with a little bit of twist you could be given a sorted array just like that but you could also be given an array that's sorted but also shifted so if you're given for example this array and the target uh you can see that it's sorted but shifted by one just like that or you could be given this array uh which is the same array but shifted by a larger amount just like that and you don't know how much your array has been shifted by when you're given this problem so you know the problem is writing a function that takes these two arguments one of these arrays as well as the target and returns the index of the target if it exists and minus one if it doesn't you should be able to solve it and of log n anyway i personally think this is a pretty interesting problem i had a lot of fun when i was solving it so i would say try solving it yourself and if you want to practice implementing it on an interactive environment uh you can check out aqua experts website and they have a lot of other problems too like 98 other problems on a variety of different topics in data structures and algorithms anyway thank you as always for watching my videos and i'll see you guys in the next one