Binary Search

hey there in this video we're going to cover what is possibly the most popular algorithm in computer science binary search is the subject of most technical interview coding questions so stay tuned we're gonna see it right here on eliminate code fear binary search is one of the most popular algorithms in computer science and rightfully so it's actually one of the fastest approaches that we have for searching through a list of things right there's a famous book it's a classic I recommend you read it's called programming pearls and in there the author John Bentley mentions that only 10% of professional programmers are able to implement binary search in an interview all right only 10% and that's also been my finding every time I ask binary search and interview the candidate kind of is not able to code this up in behind the keyboard they can explain it really well because it is a simple concept to understand my whiteboard but actually getting behind the keyboard and coding it up could be a little challenging so we're gonna get plenty of practice in the screencasts when we get there but first let's go over how this algorithm works I'll give you an example let's say we have a bookshelf of randomly placed books all right there's absolutely no order to the way the books are placed on the shelf let's say that I need to look for a book by the author Shakespeare I'd have to look at every single book on the Shelf to see if it's by Shakespeare or not right that's the linear search approach right we've already seen linear search there's no order I got to look at every single element to see which matches my condition if the books were sorted I could be much smarter in the way I approach the problem I can use binary search so to implement binary search the number one condition is the data must be sorted I'm gonna write that up here if it's not sorted we got to use linear search so in the book example let's say the books were sorted by the author's last name if I was to use the binary approach to solving that problem I'll go to the book right in the center of the shelf and see who the author is there let's say the author's last name there starts with the letter U remember we're looking for Shakespeare so we can be a hundred percent certain that any book passed you is not going to be Shakespeare so we can eliminate half of the bookshelf right we're drastically reduced the problem sighs all right if Shakespeare's on this shelf it's got to be somewhere in the first half so then we can do the same thing we can check the midpoint of this section and let's say the book there the author's last name starts with the letter e then we can be a hundred percent certain that Shakespeare cannot be before either so we can eliminate that part right so we're narrowing in on the problem by breaking the problem size in half every iteration that's how binary search works so let's implement binary search on an array let me get rid of some of these scribble here so let's say we want to search for the number 78 in this array all right that's the mystery number we want to know which index position which slot contains the number 78 right and remember in an array everything starts from index position zero goes up to the length of the array which is 10 minus 1 which is the last slot index right number 9 so the way I could do this using binary search is I can divide 9 by 2 that's going to give me 4 point 5 in math but since this is integer division the 1/2 is dropped and we're left with 4 all right so 4 is going to be the midpoint of this array the index position 4 right here right so this slot contains the number 41 of course 41 is not 78 so not only is that not our number it gives us a hint as to which direction we should be looking at so we can eliminate the first half of this array all right this is sorted this is a sorted array if it wasn't sort of we of course couldn't use binary search so keep that in mind must be sorted so this data is sorted we eliminated half of the array 78 must be in this area right so I can use the same exam midpoint strategy find the middle index position here which happens to be seven and lo and behold the number 78 is in that position all right so that's really how binary search works it falls in the category of the divide and conquer paradigm you divide the problem in half and deal with only a subset and you keep breaking the problem into smaller instances of the same problem until you arrive at the result all right so I just cleared the board here to make room for new concepts I want to go into the implementation details of binary search how would you code this up in the language of your choice and to describe those steps the individual steps I'm gonna list them in a language called pseudocode which is nothing but english sentences with more detail step by step how this algorithm operates to complete the task okay and then you can use any language of your choice to implement these steps listed in English alright pseudocode is just a way to easily communicate the steps of a computer program and we're of course going to be implementing we're going to translate the pseudocode in java and you're going to get plenty of practice doing this so here's some pseudocode lingo it's called procedure since this is a java course you can just think of this as the method binary search I just give it a name capital letters doesn't really matter what the name is but what's important here is that this method accepts two arguments X and ay all right X is the value that we're searching for and a is the value is the array in which we want to search that value in okay so we're searching for X in the given array a alright and the way I want you to think of this array is like this okay at any given point in time we're only interested in a subset of the array okay as we break the problem in half and narrow in on what we are searching for the values of the first slot as well as the second slot the index positions of those slots is going to be changing right so that's what are the variable or here represents that's the last slot of the range that we're interested in and P is going to be the first slot of the range that we're interested in and Q of course is the index position of the of the middle element all right so these PQ are our index of the range that we're interested in okay and when you need to access elements in an array you basically access them like this and you can give the index position whatever it is zero one two or a particular variable I in our case we can denote the range by P : dot dot dot R and this will represent the range that we are interested in the slots of the subset of the array alright so let's start listing out the steps here will be salga rhythm and keep in mind that this algorithm is supposed to return the index position of where we find X in the given array right if it doesn't find it it's gonna return a negative one so let's get started the first step is to give initial values to the range which is the variable P and R so we can say P originally will have the index value of 0 and R will have the index value of the length of the array minus 1 whatever the length of the array is we can say a dot length minus 1 okay that's gonna give us the last slot so we give it initial values and now the range is only gonna get smaller and how is it going to get smaller we'll have a loop in which we're going to be checking for certain conditions so step number two is we can have a while loop while P is less than or equal to R we want to do something and I'll list those steps here but what I want you to keep your mind focused on is this condition where P is less than or equal to R what does this mean well when we're searching through a range of course P is going to be the first slot and R is going to be the last slot all right so as it narrows down there's going to be a point where for if we can't find a given value in the array or it's going to try to cross over P as we're narrowing in and there's gonna be a point where it's about to cross over and we will have to exit this loop okay so as long as P is less than or equal to R we're still going to be in this loop and we're still going to be breaking the problem down in half every iteration and trying to find the X within the range okay and once it breaks out of this loop and it continues on we have we weren't able to find the value that we're searching for so this method will return a negative one so let me detail those steps here for you so in this sub step we'll say a inside of this loop the first things first we need to find the midpoint of the range so the way we can do this is we can say set Q to be P plus R divide that by two all right the does the index position of the first slot plus the index position of the last slot is going to give us the number of slots in the given range divide that by two is gonna give us the midpoint but what's important here is that we need to wrap this with this notation l and all this means is flooring the value whatever values sometimes if you get a fraction in the division you want to floor it to the whole number and we saw this in a couple of minutes ago when 9/2 was giving us a 4.5 well we dropped the half in integer division only the 4 is returned so that's exactly what this flooring operator is we only want or care about the whole number and that's going to give us the index position of the middle slot okay we denote that with the variable Q so once we get that the next step is to check whether this mid point that we got is this containing the value that we're searching for all right and if it is great we can return out of this loop and exit the method so we can say if a at the index position Q is equal to what we are searching for X then we can just return the index position of Q and we're done okay that will just exit out of this method and we've solved the problem and then the next step is see we have to consider the fact that Q did not contain the value that we're searching for and in that case it's going to move to move to step see which is if a Q is greater than X right if the value that's in this index position is greater than the value that we're searching for we know X gotta be in this direction okay and in that case what we can do is we can bring this range the second part of the range we can bring that to this slot right here because we know it can't be there it can't be in that side all right so we've reduced the range by half all right so we can say set R to Q minus 1 all right and that's going to bring if that's gonna bring the slot position here for our alright else in the case that the value here is not greater than X then the opposite is true then we know that the data that we're looking for must be in that direction and in that case we leave our where it is we change the value of P okay and we bring P over in front of our we've make point we make P point to this slot position so we can say else set P to Q plus R plus 1 sorry okay it's going to continue to narrow in like this as this loop is running the values are going to be changing it getting closer to what we are searching for and eventually this step B will find X if it is in this array otherwise step three right here is going to happen and what that is is it's just going to return negative one we were not able to find the value that we are searching for in this array all right so hopefully this makes sense let's head over to the screencast and implement this in Java

Channel: Imtiaz Ahmad

Views: 62,516

Rating: 4.8499999 out of 5

Keywords: binary Search, Java, algorithms, data structures

Id: rjwKOIK7ls0

Length: 13min 8sec (788 seconds)

Published: Sun Feb 28 2016