Binary Search algorithm in JavaScript

hey how's it going it's Lee Halladay and in my channel I create tutorials on react JavaScript and I'd love to have you subscribe if you're not already today we're going to touch on something that I typically don't cover and that's an algorithm we're going to be learning how to do a binary search in JavaScript what is a binary search it's an efficient way to find a value inside of an array so I've got a JavaScript file set up with an array of values that go from 0 to 10 so that would be 11 elements right starting at 0 all the way up through 10 and for binary search to work they have to be sorted in the right order I've set this up so it's already sorted but let's get started so if I were to make a sort of naive search algorithm it would basically be to just start at the first element index 0 and just look at the next next next next all the way to the end until I either find the value or I don't so if we just quickly write the naive approach first it will be a function that takes in the value we're looking for along with the array we're hoping to find that value in so we will create 4 haven't used these in a little while but we'll start it at 0 so the index starts at 0 and we'll keep looping as long as the index is less than the length of the array and on every iteration we will increment that index so what we want to be checking is basically to see if the value that we're searching for is equal to the element that we're currently on if that's the case we're going to return that index you I'm having a hard time typing and if that's not the case we're going to keep on searching so we'll just let it keep looping but if it gets to the end of this for loop and it hasn't found it we are going to be returning minus 1 and minus 1 will basically indicate we weren't able to find this element in the array so if we console dot log this search function passing in let's say the number seven so we're trying to find seven in the values array so if we come down to the console we were able to find the value seven at index seven it just happens that I line them up that way so it's easy to figure out but how many loops or iterations did it take to find seven we can put a consult a log on every two iteration so we basically start at index zero then we tried 1 2 3 4 5 6 7 and finally when we got to index 7 we found our value number 7 so it took us looping through as many number of elements as we could 7 define that but what if we were looking for value 15 we would literally have to look through the entire array we wouldn't find it just to return minus 1 that's not a big issue when you're array is only 11 elements long but imagine if you had 10,000 or 10 million that's a lot of iterating just to find out that the values not even there so sort of the best-case scenario would be I mean I guess on the first one but the worst-case scenario would be literally looping through every value so we want to try a better approach and the binary search approach is to always be taking our full array cutting it in half and then checking to see if our value is in the left half or the right half and that only works if it's sorted in the right order otherwise you won't be able to basically have that certainty that it's either to the left or to the right but that's what the algorithm we're going to work through right now so let's create a function called binary it will also take in the same arguments the value we're searching for and the array that we're searching that value for in and I'm gonna comment this out now and so with binary search you're always dealing sort of with the lower limit so this would be the zeroeth element and the upper limit would be the 10th element here so we'll say let lower equal zero because that's always sort of the starting point in an array let the upper be the array length minus one there we go so that would be eleven minus one would give us the tenth element which gives us this one here and what we're going to do is we are going to just keep iterating as long as the lower boundary is still less than or equal to the upper boundary so if we get to the end of this and we still haven't found it we're gonna return minus one again that indicates we weren't able to find the value in our array so what do we want to do on each iteration what we want to do is basically take the lower so zero the upper ten and we want to check the value that's right in the middle of that so the fifth one so we'll first get that index set up so the middle will be equal to our lower plus the we're gonna round down in this case because if you've got let's say nine elements what's half of nine is four point five in that case we're gonna check on the fourth element and so what we want to do is figure out how many elements are between the upper and the lower so we'll do upper minus lower so this would give us ten minus zero which is ten and we'll divide that in two which gives us five so that would be zero plus 5 gives us the middle element of five so once we have the middle element or the sorry the middle index I should say we want to just check is that equal to the value that we're looking for so is the Val equal to the array at the middle if element only middle is a word but hopefully you understand that so if that's the case great we found the one we were looking for we can return that middle element or the middle index I should say but here's where it gets complicated not that complicated two if statements we're going to cover we didn't find it in the middle so that means it's either on the left side of the middle or the right side of the middle so the first case we can handle is when our value is less than the one located at the middle a--the element if that's the case we need to basically stop looking through this whole array and we can now shift our focus to the elements on the left side of the middle because we know it's either in this side or it's not in the array at all so if that's the case we're going to reset our upper limit to basically be this one to the left of the middle so we will say upper is now equal to the middle minus one to shift it to the left of that else must mean that our element is either on the right side of the middle one or it's not there at all so we want to set the newer lower limit to be this element here which would be middle plus one so with that in case it's let's walk through a few scenarios so we'll do console.log we're gonna do the binary search what should we search for let's say seven in our values so if we run this we get back seven but that's not super useful we want to know how many iterations or how efficient was it to find the value we're looking for so why don't we just put a simple console dot log here that says try it's trying to find the element and we'll count how many times we see that try show up so with seven it took us four tries to find the number now if you remember in the old approach it actually took us seven tries to find the number so four is not so bad it's more efficient if we change it to ten which is the last one it also only took us four how is that possible in the old approach this sort of naive one it would have had the loop in iterate eleven times or to find that so how did that work so we're trying to find 10 here right so if we start we cut it in the middle is 10 equal to five no it's greater then so now we shift our focus to these elements we cut it in the middle so we look at eight is it equal no it's greater so we shift it to the right we're here there's not really there's no middle between nine and ten but you remember we took the floor so the lower one we round down so we check is it equal to nine no it's greater so we shift over here and finally we found it so it took us four tries to find any element inside of this array which is pretty cool it can obviously be a little bit faster than that like say we just happen to find the one in the middle right away great it took one try if we happen to be looking for eight it takes two tries if we happen to be searching for let's say two it also took two tries so it depends how sort of which one you're looking for and if it happens to fall on it right away but worst case scenario with this many elements it only took us four tries so even if you have ten million elements every time you're cutting it in half so you'd go from like 10 million to only 5 million to two and a half million to whatever so the worst case scenario in the naive approach would mean I have to search for 10 million iterations the worst case in and this one is a lot less because you're always just cutting it in half so that number can get pretty low pretty quickly so that's a binary search you have a sorted array you're always cutting it in half and you're either going to the left of that value or to the right of that value hope you enjoyed this video take care bye

Channel: Leigh Halliday

Views: 7,303

Rating: 4.9893332 out of 5

Keywords: javascript, binary search, algorithm, binary search algorithm, binary search algorithm explained, binary search algorithm javascript, developer interview, programming interview, interview binary search, binary search explained, binary search tutorial, beginner friendly binary search

Id: 7lGiPItOVCM

Length: 11min 3sec (663 seconds)

Published: Thu Jan 16 2020