Algorithms: Binary Search

Key Takeaways

hi I'm Gail lock McDow author of Kraken coding interview today we're going to cover binary search so binary search is a very intuitive algorithm and I'm going to show how intuitive It Is by giving an example you're a teacher and you're teaching a group of students a very large class of 300 students and you have their papers alphabetized out in front of you when a student Zack Peters comes up to get for get his paper back so you probably wouldn't go through the papers starting with Alex to an to Andrew and then to Bob and Brenda and Brandy and then to Chris and Christine and uh you probably wouldn't do it that way what you'd probably do is open the paper open the stack of papers to roughly halfway through the papers and compare it Zack Peters well that you open up halfway through and you see Michael matters there and you'd say Okay Zack Peters is after that name and then you take the second stack of papers and you'd treat it as its own little stack and you'd again say okay let me open up to its midpoint maybe we see Sarah well is Sarah before or after Zack Peters and then you just go and repeat this process over and over and over again until you find Zach's paper or until you find out Zach can't be in here and this is the basics of binary search so on an integer array it looks like this you take some element that you're looking for like 13 and you compare it to the midpoint and it has to be a sorted array for this to work it's very important you compare it to the midpoint 13 is less than this midpoint and so 13 if it's in the array at all it has to be on the left side and then You' repeat this process on the left side and say let me look at the midpoint of the left side it's 13 before and after that before after that and you just repeat that process until you either find 13 or you know that 13 can't be in it so how fast is this algorithm well let's imagine we start off with n elements so we have a search space of n elements in a single comparison just one we've cut our search space down to n/ two then with one more comparison we cut it down to n/4 and then and half again and half and half and half and half again so how many total operations in the very worst case will we have to run until we figure out if it contains an element or not well the total number of operations we'll have to do is determine by how many times can we divide n by two until we get down to just one so this is what log of n expresses or log base 2 of n expresses so and if you pause the video you can study that math for a second and see the relationship between those two things but this means that binary search is a log n problem let's look now at the implementation of binary search to implement binary search we can either implement it recursively or iteratively we'll do a cursive implementation first so I'm going to just copy and paste here some uh just straightforward code for the binary search call so this is a you know initial method that calls off to this binary search recursive method with the right parameters so we're going to start off initially with left being zero and right being the very right point so these are inclusive end points so first of all if things get kind of too big if left winds up bigger than right then we know we have an error we can't find it and we want to return true otherwise we want to pick the midpoint so left. right divided two that's going to be the midpoint and if we found the element if array of mid is actually this element we're looking for then we should return true otherwise if x is on the left side of mid then go search the left side uh so pass an array X and left will stay as is and the right point will mid will move to one next to the mid otherwise go search the right side so we want to call very similar method but now the left Point moves up to Mid + one and right stays as is okay so that's how the binary search recursive implementation looks so one little minor Pitfall is that some and some people like to be careful of is that left plus right can actually overflow with Java integers so if you'd like to avoid the integer overflow issue you can actually just do this instead and this will prevent the Overflow it's kind of up to up to you but this is one way of doing it okay so now that we've done the recursive implementation let's turn to the iterative implementation so what I'm going to do is I'm going to actually tweak this recursive implementation I'm going to copy paste it into a new function and I'm going to tweak it to make it iterative so I'm going to call this iterative and I no longer need parameters in here but what I'm going to do is I'm going to set so I'm going to show you how you can kind of tweak it so I'm going set left to be that right is going to start off at the rightmost position in the array so now I want to iterate as long I want to Loop through this as long as left and right are essentially in the correct positions so change this to a while loop all right and then if I exit here then I haven't found it okay so this looks correct and then here I don't want to actually recurse anymore what I want to do is essentially take these values here so left is going to stay as is and right is going to move to Mid minus one comment that out and I'll delete it shortly and then here rather than so left is going to stay or left is going to become mid + one and right is going to stay as is so that's how easy it is to tweak it from recursive to iterative so that's how we Implement binary search now remember that it can be implemented recursively or or itly and it can also be applied to other data like strings or something else but it must always operate on something that's sorted so now that you've seen the implementation of binary search why don't you try to do binary search on a new data type like a string good luck