# How and Why of Binary Search

Published on Apr 17th 2023Duration: 46:33Watch on YouTube

This is a CS mentoring session I did with Carol where we covered the how and why of the binary search algorithm. We did the session over repl.it and we even asked Ghostwriter - the repl.it AI what binary search is!

## Transcript

The following transcript was automatically generated by an algorithm.

• 00:00 : one two four eight Seventeen thirty five
• 00:05 : let me I mean how would you characterize
• 00:08 : this curve if I increase just one of my
• 00:12 : steps then I can double the number of
• 00:15 : elements I can take on first I'm gonna
• 00:18 : flip this
• 00:20 : uh horizontally
• 00:22 : and then I'm going to rotate this 90
• 00:25 : degrees to direct
• 00:27 : and voila hello what you're going to be
• 00:30 : seeing is a mentoring session I did with
• 00:33 : Carol in which we go over the binary
• 00:36 : search algorithm this video is unedited
• 00:40 : um if you find parts of it slow then
• 00:43 : feel free to skip ahead
• 00:46 : okay I'm gonna ask Ghostwriter
• 00:49 : um
• 00:52 : uh what is
• 00:55 : binary search
• 01:00 : binary search is an algorithm used to
• 01:02 : search for an element in a sorted array
• 01:05 : or list by repeatingly dividing the
• 01:09 : search interval in half
• 01:11 : until the element is found or the search
• 01:14 : interval is empty
• 01:17 : it works by compare the comparing the
• 01:20 : target value to the middle element of
• 01:22 : the array
• 01:24 : um
• 01:25 : maybe I should
• 01:27 : I I'll ask it to can you illustrate that
• 01:35 : illustrate the algorithm
• 01:40 : I'm making it to my job
• 01:42 : yeah
• 01:45 : okay it is not able to draw pictures as
• 01:49 : I understand I think gpt4 might be able
• 01:52 : to do pictures
• 01:54 : but this is not gbt4 level this is this
• 01:59 : is chat GPT level
• 02:01 : okay
• 02:02 : um I'll have to try that out with gpt4 I
• 02:05 : didn't know it it maybe had that
• 02:07 : capability to write draw pictures that's
• 02:09 : cool
• 02:10 : you need to pay twenty dollars a month
• 02:12 : to get GPT for yeah I have it that's
• 02:16 : sweet
• 02:18 : I'm a sucker
• 02:20 : cool
• 02:22 : um
• 02:22 : let's see so diagram that
• 02:27 : yeah I think I wanna
• 02:32 : pay for it try it out as well
• 02:37 : um okay
• 02:39 : so I'm gonna take a look at what it's
• 02:41 : saying and try to draw the diagram
• 02:45 : um um do you see me in the rebel because
• 02:47 : I'm not able like usually when I have it
• 02:50 : open I can see what you're drawing on my
• 02:52 : screen like not the shared screen but
• 02:54 : I'm not seeing it today
• 02:56 : not seeing the the
• 02:59 : hook try clicking on my avatar and say
• 03:03 : observe me
• 03:04 : okay
• 03:08 : try
• 03:12 : yeah it's not giving me that option
• 03:16 : it's okay I'll just look through the
• 03:18 : through the shared screen on the um
• 03:21 : I'll make that work that's fine
• 03:23 : okay so
• 03:25 : um so first given a list of given a
• 03:30 : sorted list of elements
• 03:32 : so you you actually have to
• 03:34 : prism they're already sorted
• 03:37 : okay that's a requirement of this
• 03:40 : algorithm
• 03:42 : might be faster to draw the lines
• 03:47 : I used to have a stylus but I don't
• 03:50 : anymore oh I don't have it with me
• 03:54 : um
• 03:55 : so to get a sorted list of uh so let's
• 04:00 : say I have
• 04:02 : I don't know
• 04:04 : uh one
• 04:10 : uh
• 04:12 : okay I'll do it like this one three five
• 04:16 : eight twelve
• 04:19 : 27 50.
• 04:23 : eight
• 04:24 : hundred
• 04:26 : um so it's presumed that you already
• 04:29 : have them sorted that's important
• 04:32 : how you get it sorted I don't care uh
• 04:36 : you might have to study the the array
• 04:39 : sorting algorithms
• 04:41 : um
• 04:43 : um and and then the goal is you want to
• 04:47 : find a particular value in this array so
• 04:52 : that the the
• 04:54 : like
• 04:55 : you're implementing the find method so
• 04:59 : something like
• 05:00 : well okay not the JavaScript it's fine
• 05:04 : because that's kind of different uh
• 05:08 : maybe I should say like
• 05:10 : binary
• 05:12 : because it was a normal array it's not
• 05:15 : presumed that they're already sorted
• 05:17 : right right so you can't do you can't
• 05:21 : have a normal array implement this but
• 05:25 : um but let's say there's a sorted array
• 05:28 : and I can
• 05:30 : binary search find
• 05:34 : some value
• 05:37 : maybe I want
• 05:38 : 27
• 05:41 : um and then it will give me the index of
• 05:44 : 27 as a return value and and if I if I
• 05:52 : uh for something that's not in there
• 05:56 : then it will give me a negative one
• 05:59 : okay so for 27 it'd be a zero one two
• 06:02 : three five six this will give me six
• 06:06 : um so that's what we're trying to do
• 06:08 : um now it could be more useful if
• 06:11 : each cell also has attached additional
• 06:15 : information in it
• 06:18 : um
• 06:19 : then then you could use sort of this
• 06:23 : value as an index into that information
• 06:28 : if that makes like if each one was like
• 06:30 : a person for example
• 06:32 : and then the number was the person's ID
• 06:36 : then you binary search fine dot by the
• 06:40 : ID will give you additional information
• 06:42 : about that person
• 06:44 : okay so so that's more practical use
• 06:47 : case
• 06:49 : um
• 06:50 : so what what Ghostwriter is saying is um
• 06:55 : we're gonna have left and right pointers
• 06:57 : that point to the start and the end of
• 07:00 : the list
• 07:01 : respectively so this is the start
• 07:04 : pointer
• 07:05 : and I mean there's the left pointer and
• 07:08 : this is the right pointer okay and then
• 07:11 : we're going to calculate the middle
• 07:13 : index by taking the floor division
• 07:16 : uh this the sum of left and right
• 07:19 : pointer and divided by two basically
• 07:22 : we're trying to get to the middle more
• 07:24 : or less
• 07:25 : but but because like um the reason it's
• 07:29 : it's a it's an average like left at this
• 07:32 : point is going to be zero
• 07:36 : and right is is going to be zero one two
• 07:40 : three four five six seven eight is gonna
• 07:43 : be eight here
• 07:45 : so in order to find the middle
• 07:47 : you do take the average of the numbers
• 07:50 : so zero plus eight divided by two is
• 07:53 : four so you end up here
• 07:58 : okay and that's going to be your middle
• 08:09 : and um
• 08:11 : and basically your
• 08:14 : like what's the point of this looking at
• 08:17 : the middle well you can compare your
• 08:19 : target to the number in the middle
• 08:24 : um and if your target is greater than
• 08:27 : the number in the middle
• 08:29 : then you know it's gonna be to the right
• 08:32 : of that if it's less than the number in
• 08:35 : the middle you know it's going to be to
• 08:38 : the left right
• 08:39 : right
• 08:41 : so yeah so in this case
• 08:44 : um it is to the right
• 08:46 : and then then what you're gonna do is
• 08:49 : you're gonna replace the left pointer
• 08:52 : with the middle pointer so you are
• 08:54 : another way of saying is you're moving
• 08:57 : the left pointer
• 08:58 : to to be the middle pointer I see
• 09:03 : and then you you and then you do the
• 09:06 : process again you find the middle
• 09:08 : pointer again
• 09:09 : which should be
• 09:11 : the middle more or less but if we were
• 09:14 : to it with the formula it would be four
• 09:16 : plus eight twelve divided by two which
• 09:20 : is six I believe that's this like zero
• 09:24 : one two three fives oh no
• 09:27 : but zero one two three four five six
• 09:31 : yeah this is this is right
• 09:34 : um so this is six
• 09:37 : and we're gonna compare our Target with
• 09:40 : 27 uh with 50. but 27 is less than 50.
• 09:45 : so we know it's going to be to the uh
• 09:49 : left
• 09:51 : the the but to the right of the four
• 09:55 : right because we already did that
• 09:57 : comparison so it's in is inside this
• 09:59 : range
• 10:02 : um uh so for that reason this time we're
• 10:05 : gonna move the right pointer
• 10:08 : over to replace the middle pointer
• 10:13 : so the right pointer is here now
• 10:16 : and now we're going to do the same
• 10:17 : process again
• 10:19 : and we're gonna see that the middle is
• 10:22 : here now
• 10:23 : and we're gonna hit the target
• 10:27 : and then when we hit the target we know
• 10:30 : that this we found it
• 10:32 : and in our simple example we're just
• 10:35 : going to return the index
• 10:37 : of of that middle uh pointer
• 10:46 : um yep so that's the case where we've
• 10:50 : found the thing let's try the case where
• 10:52 : we don't find the thing
• 10:54 : okay
• 10:56 : um
• 10:58 : so we start here and I start here we're
• 11:01 : looking for 45 this time okay
• 11:07 : um and so again we're gonna find the
• 11:11 : middle
• 11:12 : and um
• 11:15 : 45 is greater than that so we're gonna
• 11:18 : replace the
• 11:19 : uh left Arrow we move the left Arrow
• 11:23 : over here to the middle Arrow
• 11:25 : and now again we're gonna take the
• 11:28 : middle
• 11:29 : stat and then 45 is less than 50.
• 11:34 : so we're gonna
• 11:36 : move the right arrow to the this spot
• 11:40 : and then finally we go here
• 11:43 : we see that 45 is greater than
• 11:47 : 27.
• 11:49 : and now the right thing to do would be
• 11:52 : to
• 11:54 : move the left Arrow over and then look
• 11:58 : into the middle here
• 12:00 : uh but there's actually nothing in the
• 12:02 : middle
• 12:03 : because because the left and right
• 12:06 : arrows are right next to each other
• 12:08 : they're adjacent so you can put in a
• 12:11 : check
• 12:12 : to see that they're adjacent that
• 12:16 : there's nothing in between them and if
• 12:18 : that's the case
• 12:19 : that means you've exhausted the search
• 12:21 : you know that the target isn't in this
• 12:24 : array and you return negative ones
• 12:28 : cool
• 12:30 : um or I think this algorithm
• 12:34 : let me see
• 12:37 : uh if the target is the same if the
• 12:41 : target is smaller blah blah blah
• 12:42 : continue this process until the target
• 12:45 : element is found or the search interval
• 12:49 : is empty so yeah
• 12:51 : so we can we can say if if left
• 12:55 : and right is only a part by one
• 12:58 : then the search interval is empty
• 13:03 : that makes sense
• 13:05 : yeah yeah
• 13:07 : um that's that's the binary search
• 13:09 : algorithm
• 13:11 : um
• 13:13 : why is this algorithm
• 13:16 : interesting
• 13:22 : um it's very creative
• 13:25 : way of doing things
• 13:28 : um why is it interesting
• 13:33 : it is interesting I like it I don't I
• 13:36 : don't know
• 13:37 : well um why like it's it's definitely
• 13:41 : like yeah it's creative
• 13:44 : um
• 13:46 : in
• 13:48 : like it's it's it's creative but what's
• 13:51 : the gain
• 13:53 : of like what is the creativity trying to
• 13:58 : uh like why are you trying to be clever
• 14:05 : straightforward way
• 14:07 : what would be a what would be a more
• 14:10 : straightforward way to do this yeah so a
• 14:13 : more straightforward way would be
• 14:15 : iterating through each element in the
• 14:18 : array and this alternative
• 14:23 : um seems like it really cuts out a lot
• 14:25 : of the work you know it's it's we don't
• 14:27 : going on the principle that we don't
• 14:30 : want to be
• 14:31 : searching through elements if we can
• 14:34 : eliminate the need like it's eliminating
• 14:36 : the need to search through large chunks
• 14:40 : um that's true yeah so it's improving on
• 14:43 : the performance yeah yeah or to reducing
• 14:46 : the amount of work
• 14:49 : I actually really like the in computer
• 14:53 : science
• 14:55 : um
• 14:57 : when you're working on performance
• 15:01 : it always means reducing the amount of
• 15:05 : work
• 15:08 : um
• 15:08 : but I I think the word performance
• 15:13 : in general
• 15:15 : has the connotation of
• 15:19 : uh
• 15:21 : you're just buying real hard
• 15:24 : or you know like to run fast or you're
• 15:29 : putting a lot of muscle into it or even
• 15:32 : a lot of power into it yeah
• 15:35 : um
• 15:36 : because
• 15:37 : I guess that's what we think of when you
• 15:40 : think of like at performance in athletes
• 15:44 : um or or maybe in other like Machinery
• 15:48 : or like you put more voltage
• 15:51 : or a bigger engine behind it right yeah
• 15:56 : performance is usually seen as more
• 16:01 : power well even in Computing uh you
• 16:04 : could put more Hardware behind it you
• 16:06 : could put a faster CPU behind it
• 16:09 : uh more servers
• 16:12 : Etc and that that is true
• 16:14 : but um so maybe maybe it's not always
• 16:18 : true in computer science that there's
• 16:20 : this power based
• 16:22 : strategy in computer science too but but
• 16:25 : I I really like
• 16:28 : um when you're dealing with algorithms
• 16:31 : and you're working trying to improve
• 16:33 : performance
• 16:34 : that you're actually trying to reduce
• 16:36 : rather than increase
• 16:39 : uh that that I just uh that that's very
• 16:42 : Zen for me yeah I agree I agree it's
• 16:46 : like how what's the the way we could do
• 16:49 : this with the least possible effort or
• 16:52 : the least possible use of resources like
• 16:55 : it's a cool principle to just think
• 16:58 : yeah
• 16:59 : um so now we want to try to quantify
• 17:03 : this actually
• 17:05 : so like how much less work are we doing
• 17:11 : compared to the naive method
• 17:14 : of just looking at every single element
• 17:16 : so I want to get the Big O of this oh
• 17:22 : first like
• 17:24 : what what is the Big O of just going
• 17:27 : through every element
• 17:29 : and looking at everything and it's going
• 17:32 : to be it yeah so
• 17:35 : I'm gonna write down two if just
• 17:40 : look
• 17:42 : through all elements
• 17:45 : is bigger event
• 17:47 : uh what about the Big O of binary search
• 17:52 : questions
• 17:53 : that one I'm still mulling over because
• 17:55 : my initial thought was if you have a
• 17:58 : humongous list you're going to have to
• 18:00 : do this and you are going to have to do
• 18:02 : do the process more times you're gonna
• 18:04 : have to repeat the the algorithm of
• 18:08 : you know I think but as I'm sort of
• 18:11 : saying that out loud and talking through
• 18:13 : it I'm like wait is that actually true
• 18:15 : uh here we have you do get an intuitive
• 18:18 : sense that the more elements still means
• 18:22 : more work yes but not if it was like if
• 18:26 : we were doing a binary search on 10
• 18:29 : elements
• 18:30 : you do some amount of work again we
• 18:33 : should think about worst case scenario
• 18:37 : um but um no you can get lucky and then
• 18:40 : the first try you hit the target for
• 18:42 : example
• 18:43 : um but um
• 18:44 : but what if you were doing binary search
• 18:46 : on a million elements how how many
• 18:51 : tries or how many iterations of this
• 18:54 : binary search process which you have to
• 18:56 : do
• 19:00 : um what what is your
• 19:02 : do you have an intuition about
• 19:06 : what like how much more a million is
• 19:10 : versus a hundred versus ten
• 19:15 : yeah I'm thinking about it okay so in
• 19:17 : all instances you're gonna have to find
• 19:20 : the middle you're finding the middle
• 19:22 : that has to happen every time no matter
• 19:23 : what and then
• 19:27 : your middle then you're finding the
• 19:30 : middle of the accepted
• 19:32 : path
• 19:35 : I'm just I'm still thinking through it
• 19:37 : I'm still it just takes me a minute to
• 19:39 : sort of walk my brain through okay the
• 19:41 : process I I think okay so
• 19:45 : if you had a million
• 19:47 : you find approximately you find the the
• 19:51 : 500 000 slide
• 19:54 : yeah okay let me hold on I'm gonna write
• 19:58 : this down
• 20:03 : these are worth a million okay
• 20:06 : and then your first attempt you're gonna
• 20:10 : hit
• 20:11 : uh maybe I should write it uh uh so by
• 20:16 : any means search for a million
• 20:21 : elements
• 20:24 : um
• 20:29 : um and I want to say like step one
• 20:33 : we're gonna
• 20:35 : check uh five
• 20:40 : well five hundred thousand as the middle
• 20:42 : right yes so it was step one we're
• 20:46 : checking five hundred thousand
• 20:48 : uh what about step two except step two
• 20:51 : we're gonna continue to divide it in
• 20:54 : half every time so step two we're going
• 20:56 : to be down to 250 250 000 elements yeah
• 20:59 : that we still have to look through oh no
• 21:02 : I'm writing down the middle pointer
• 21:08 : but
• 21:14 : because okay maybe maybe we say this
• 21:18 : so after step one
• 21:23 : then we have 500 000 left
• 21:28 : we could say it like this
• 21:32 : and then uh step two
• 21:35 : we're gonna have uh
• 21:38 : 250
• 21:40 : 000 left and then after step three
• 21:43 : divided by two is like that ish
• 21:51 : um
• 21:52 : approximate and then what is this
• 21:55 : divided by like 70 70 something sorry
• 22:03 : [Music]
• 22:05 : XX
• 22:07 : these are probably x-axis
• 22:11 : um and then
• 22:14 : uh the next one maybe I should
• 22:18 : consult my calculator
• 22:22 : uh three six two
• 22:28 : um
• 22:28 : and then
• 22:31 : divided by two one eight
• 22:36 : and then we divided by two again
• 22:40 : nine thousand something
• 22:44 : uh let's go all the way I think
• 22:48 : 4 000 something 45 Something
• 22:54 : um
• 22:55 : to
• 23:00 : 2200
• 23:04 : uh hold on let me move my
• 23:07 : okay
• 23:12 : okay
• 23:14 : two two twenty
• 23:18 : twenty two hundred ish yeah yeah 100 ish
• 23:24 : divided by two divided by two one
• 23:28 : thousand a hundred
• 23:35 : five hundred something 566
• 23:43 : 200
• 23:48 : 140
• 23:52 : 2014 yeah
• 23:56 : and then
• 23:59 : 70
• 24:00 : we're getting close yeah uh it's 45
• 24:05 : I don't know 35
• 24:08 : uh
• 24:11 : my my son would be into this yeah
• 24:17 : 17
• 24:20 : .
• 24:23 : 8
• 24:26 : then four
• 24:29 : and then two
• 24:31 : and then one
• 24:34 : so it took us
• 24:37 : 20 iterations
• 24:40 : to find a needle and a haste of of a
• 24:44 : Million numbers
• 24:49 : so
• 24:51 : okay so two things are going on in my
• 24:53 : head after sort of stepping through this
• 24:55 : I I want to say my instincts is to say
• 24:59 : that this is still going to be Bingo of
• 25:02 : n because it does grow the steps the
• 25:04 : iterations grow exponentially depending
• 25:07 : on how many you're looking through but I
• 25:10 : know that this is much more
• 25:12 : performant much more effective than just
• 25:16 : the straight
• 25:18 : um what did we call it just the straight
• 25:20 : like iteration the the obvious iterating
• 25:23 : through every single one so it doesn't
• 25:25 : seem right they would have let me ask
• 25:29 : you this hold on
• 25:31 : let me ask you this
• 25:33 : um
• 25:35 : first of all this is worst case
• 25:39 : true in the worst case
• 25:42 : in order to search through one million
• 25:45 : things
• 25:46 : I have to
• 25:48 : do the same thing 20 times repeatedly
• 25:53 : and then the second thing I would
• 25:56 : uh make the point of is
• 26:00 : what if I want to search through two
• 26:05 : million things
• 26:07 : how does that change this answer
• 26:14 : um okay so then
• 26:17 : okay so we're just gonna have more steps
• 26:20 : because we're starting out at a higher
• 26:23 : number
• 26:24 : no how many more
• 26:27 : um
• 26:29 : we already did one million yeah one
• 26:32 : million took us
• 26:34 : 20 steps or about 2 million
• 26:38 : I want to say it's double but I don't
• 26:42 : know if that's true that might not be
• 26:44 : true you kind of think it out now
• 26:50 : well
• 26:52 : uh if we started with one million and
• 26:57 : after one step
• 26:59 : we only had 500 000 left to look through
• 27:03 : oh so it's just one more step one one
• 27:06 : every time it's one more yeah that I
• 27:09 : yeah duh because it's you're dividing in
• 27:12 : half every time
• 27:14 : so each time you double the number of
• 27:18 : elements so look through you add one
• 27:20 : step
• 27:21 : exactly
• 27:23 : now what what if
• 27:24 : what about our naive algorithm
• 27:28 : to go through all the elements
• 27:31 : um well
• 27:33 : in the worst case
• 27:36 : looking through a one million elements
• 27:38 : will take one million steps
• 27:41 : right
• 27:43 : what about looking through two million
• 27:46 : elements yeah it's gonna double it's
• 27:48 : gonna be it's gonna double the number of
• 27:50 : steps whereas with the binary search
• 27:53 : when you double the elements it only
• 27:56 : increased one step
• 27:58 : yeah that's insane right it's a lot
• 28:02 : better yeah
• 28:03 : yeah
• 28:04 : that I mean so so there's no way you can
• 28:08 : tell me this is not better
• 28:10 : yeah for sure
• 28:12 : it must be much better yeah but the
• 28:15 : question is
• 28:17 : um how do you Quantified quantify this
• 28:20 : better
• 28:22 : um
• 28:23 : well
• 28:27 : um
• 28:35 : let's think so hmm
• 28:40 : you think about how to
• 28:43 : do this like
• 28:46 : um
• 28:51 : maybe we should
• 28:52 : hmm
• 28:57 : numbers
• 29:00 : what
• 29:02 : pattern
• 29:03 : okay
• 29:05 : like what how would you describe this
• 29:08 : trend
• 29:09 : like one two four eight
• 29:13 : 1735
• 29:15 : yeah it's doubling every time you go up
• 29:19 : like like
• 29:20 : every time you go up a step from
• 29:23 : starting at 20 our numbers are just
• 29:25 : doubling every time
• 29:27 : yeah if we were to plot it would be like
• 29:32 : uh
• 29:34 : one
• 29:36 : two
• 29:38 : four
• 29:40 : eight
• 29:42 : sixteen
• 29:45 : thirty two
• 29:48 : uh it's too high for me to draw it now
• 29:51 : uh so
• 29:54 : let me I mean how would you characterize
• 29:57 : this curve with a word
• 30:00 : sharp like sharp fast rising yeah so
• 30:04 : this is exponential this is like this is
• 30:07 : two to the x
• 30:10 : basically this is a equation in math
• 30:13 : terms this is two to the
• 30:16 : 2 to the x or two to the 2 to the N if
• 30:19 : we want to use the letter N which which
• 30:22 : is exponential the the variable is the
• 30:26 : exponent
• 30:27 : therefore it's it is exponential
• 30:32 : um
• 30:34 : but
• 30:37 : but actually the thing
• 30:42 : but exponential would be very bad for a
• 30:45 : Big O
• 30:47 : and that's not what we have because
• 30:52 : um it's only it's exponential but
• 30:56 : um
• 31:01 : the um the the number of steps we have
• 31:04 : to take the exponential is like we're
• 31:08 : describing
• 31:09 : the number of elements we're dealing
• 31:11 : with
• 31:13 : so
• 31:18 : so as we increase the number of steps
• 31:23 : like we were starting with a number of
• 31:24 : elements before
• 31:26 : but
• 31:27 : now let's do the reverse and say
• 31:31 : if I increase
• 31:34 : just one of my steps
• 31:37 : then I can double the number of elements
• 31:40 : I can take on right right
• 31:44 : so every time I increase the number of
• 31:46 : my step
• 31:48 : I can double the number of elements I
• 31:51 : can search through
• 31:52 : and that rapidly grows
• 31:56 : um
• 31:57 : so it means every additional step gives
• 32:00 : me so much more power a lot more double
• 32:03 : the amount of power
• 32:05 : um
• 32:06 : and and and so if we want to describe
• 32:09 : the
• 32:12 : um
• 32:13 : the number of steps
• 32:15 : that are required
• 32:17 : to
• 32:19 : uh search through
• 32:21 : n elements
• 32:24 : it's actually the inverse
• 32:26 : of an exponential
• 32:29 : okay okay so so if I ask you what
• 32:35 : relative to the number of elements I
• 32:39 : need to search through how many steps do
• 32:42 : you need to take
• 32:45 : then you're solving for
• 32:47 : um
• 32:48 : good
• 32:52 : uh uh
• 32:55 : make some space here
• 32:59 : um so so given
• 33:02 : let me zoom in
• 33:10 : given I want to search through search
• 33:16 : n elements
• 33:20 : how many steps
• 33:23 : do I have to take
• 33:26 : uh
• 33:28 : so that's like the inverse
• 33:31 : um of an exponential and what what is an
• 33:34 : inverse of an exponential
• 33:36 : so you can try to imagine
• 33:41 : the number of steps
• 33:44 : number of steps I mean sorry number of
• 33:47 : elements is
• 33:49 : uh uh two
• 33:52 : to the power of
• 33:57 : um how do I write power in this thing
• 34:00 : maybe what I do is 2 to the power of uh
• 34:05 : uh to the power of s
• 34:08 : so 2 to the power of s
• 34:11 : let's see
• 34:13 : where s is the number of steps so number
• 34:16 : of elements is n
• 34:18 : n is 2 to the power of s I kind of want
• 34:23 : to do it
• 34:25 : like
• 34:27 : I'm gonna try to do it as a superscript
• 34:31 : see if I can do that
• 34:35 : s
• 34:38 : and I'm gonna move it over here
• 34:41 : is that that works that works okay so
• 34:46 : yeah n is 2 to the power of S and S is
• 34:50 : the number of steps and N is the number
• 34:53 : of our elements in the array
• 34:56 : um so my question is given an N an N
• 35:00 : could be 500 and could be a million what
• 35:04 : is the s
• 35:06 : that you're gonna need
• 35:09 : and the mass equation for that is
• 35:14 : s is equal to
• 35:17 : the log base 2 of n
• 35:25 : okay so if if you find the log base 2
• 35:29 : function in your calculator
• 35:31 : uh do I have this
• 35:38 : [Music]
• 35:38 : um
• 35:41 : so do I have vlog
• 35:47 : uh log look I have log base 10.
• 35:52 : uh this is a lot oh uh like I think you
• 35:56 : have to do it convert
• 35:58 : log base 2.
• 36:00 : and I don't remember how to I'm not good
• 36:02 : at math so I don't remember how to do it
• 36:05 : off hand
• 36:06 : log
• 36:08 : base 2
• 36:11 : yeah there's a log base 2 calculator I'm
• 36:16 : gonna use or I could have asked actually
• 36:19 : I have three free
• 36:21 : messages remaining so what is uh one
• 36:27 : million
• 36:30 : what is log base 2
• 36:33 : of
• 36:35 : 1 million
• 36:43 : it's
• 36:45 : 19.9 which is the 20 steps that we took
• 36:48 : yeah
• 36:49 : yeah so so the equation we're after all
• 36:54 : along is uh is log log algorithm
• 36:59 : or the log function I should say
• 37:02 : um and a log function is
• 37:05 : um
• 37:07 : I forgot to describe it is the inverse
• 37:09 : of an exponential
• 37:12 : um and it
• 37:15 : um I'll just Google for
• 37:18 : plot of log function
• 37:26 : yeah a log function looks like this
• 37:30 : if you if you plot it and you can see
• 37:34 : it grows like this
• 37:37 : and it grows very very slowly and the
• 37:40 : the the the the more to the right like
• 37:43 : that as the number grows like to a
• 37:47 : million to 2 million 10 million
• 37:50 : it continuous growth but it is almost
• 37:53 : flattens not quite but it's it's growing
• 37:56 : so slowly
• 37:59 : um versus uh Big O of n would be just be
• 38:03 : a diagonal line diagonal yeah
• 38:05 : that goes like that so a log line is
• 38:09 : like this
• 38:11 : and that's much much cheaper you can
• 38:13 : just see it
• 38:15 : yeah
• 38:17 : yeah for sure
• 38:19 : hey there this is Toby from another
• 38:21 : point in time I have an addendum to make
• 38:24 : to the to this video because I thought
• 38:27 : of a better way to illustrate the log
• 38:30 : function curve so this is the
• 38:34 : exponential function curve as we have
• 38:37 : plotted
• 38:39 : um
• 38:40 : because the log curve is simply a the
• 38:43 : log function is simply an inverse of
• 38:46 : this curve we can actually arrive at
• 38:48 : that by flipping and then rotating this
• 38:52 : image so first I'm going to flip this
• 38:55 : horizontally and then I'm going to
• 38:58 : rotate this 90 degrees to direct
• 39:02 : and voila we have the log graph so if
• 39:06 : you remember we were plotting this guy
• 39:10 : um
• 39:11 : here
• 39:14 : formerly the y-axis but now the x-axis
• 39:18 : we were plotting n which is the number
• 39:21 : of elements in an array and then over
• 39:25 : here
• 39:26 : formerly the x-axis but now the y-axis
• 39:30 : is s
• 39:33 : so the number of steps
• 39:35 : required in order to search Three N
• 39:39 : elements and you can see that if we had
• 39:44 : to search through n equals eight say
• 39:47 : this that was for the number eight
• 39:50 : then the number of steps required to
• 39:52 : search through it would be four
• 39:56 : and as we doubled the number of elements
• 40:00 : here we go to 16
• 40:03 : then the number of
• 40:06 : steps required to search through it
• 40:08 : would be five and if it's in between say
• 40:12 : a number like 10 then we just get a
• 40:15 : point in between four and five this is I
• 40:19 : think a much more intuitive way to
• 40:21 : arrive at the log function curve so yeah
• 40:26 : so the answer to the original question
• 40:28 : what what is the Big O of the binary
• 40:30 : search algorithm
• 40:33 : um is
• 40:35 : it's the the Big O of log of n
• 40:39 : uh
• 40:42 : log base 2 of n to be more precise
• 40:46 : but um
• 40:48 : that's not super important the the fact
• 40:51 : that is log base 2 because it's binary
• 40:54 : right we're dividing two every time uh
• 40:57 : you potentially you could generalize
• 40:59 : this to log any number like
• 41:02 : like when I asked my son by the way this
• 41:07 : this is very applicable to um to guess a
• 41:11 : number game
• 41:13 : so so so the guesser number game is like
• 41:17 : I'm I'm thinking of a number between
• 41:20 : zero and a million
• 41:23 : can you guess what the number is
• 41:27 : and and I'll give you 20 tries
• 41:33 : [Music]
• 41:34 : uh
• 41:36 : yeah but then you have to get the person
• 41:39 : to tell you whether it's higher or lower
• 41:40 : than your guess correct yeah I I do I do
• 41:44 : have to tell you whether it's higher or
• 41:46 : lower yeah yeah exactly so now when I
• 41:49 : ask my son this
• 41:51 : uh guess a number game problem
• 41:54 : uh his intuition was
• 41:57 : well I guess
• 42:00 : um
• 42:02 : sort of
• 42:04 : um
• 42:07 : he's thinking in base 10 basically so
• 42:10 : he's thinking like I'll first try
• 42:14 : a hundred thousand
• 42:17 : and then I would try two hundred
• 42:19 : thousand
• 42:21 : depends like like if if a hundred
• 42:24 : thousand is low then I'll try two
• 42:28 : hundred thousand and if that's still low
• 42:30 : I'll try 300 000 right
• 42:33 : yeah so he's thinking of subdividing it
• 42:36 : by 10 instead of subdividing it by two
• 42:40 : and it still works yeah it's the same
• 42:43 : idea but because we human beings are
• 42:47 : trained to think in base ten we we uh
• 42:51 : we're more naturally gravitate toward
• 42:53 : subdividing it by 10.
• 42:56 : um but yeah but but you know binary is
• 43:00 : because computer science tests think in
• 43:03 : binary
• 43:05 : so yeah so this is natural for them
• 43:08 : uh yeah and uh
• 43:11 : so so that that is why
• 43:13 : um and I can tell you that
• 43:17 : yeah this this is so related to the
• 43:20 : guess a number game but well with the
• 43:22 : hint every time you get it wrong you get
• 43:24 : the hint
• 43:26 : um
• 43:27 : and I actually asked
• 43:29 : uh chat TPC this gets the number again I
• 43:32 : asked it to play guess a number with me
• 43:34 : and it immediately spit out this uh
• 43:38 : binary search algorithm to me hahaha
• 43:41 : yeah but everyone gets a number for me
• 43:45 : though I try to get it to play with me
• 43:47 : but it'll just draw out like this is
• 43:50 : what the scenario would look like like
• 43:52 : he spelled out the whole story but he
• 43:54 : wouldn't play with me
• 43:55 : oh funny japanese he won't play games
• 43:58 : all working no play yes exactly
• 44:02 : um
• 44:03 : um okay so I guess yeah so so usually we
• 44:07 : don't write the log two we just say log
• 44:09 : of n okay
• 44:12 : um and I guess the moral of the story is
• 44:17 : that log of n is much much better than n
• 44:23 : it's not even close it's um so the only
• 44:27 : thing that's better than log of n is log
• 44:29 : of one oh sorry it's big old log N is a
• 44:33 : bit of log one
• 44:34 : um and whenever we want to
• 44:40 : whenever we want to get something to
• 44:44 : work super fast in Computing
• 44:48 : we're all always aiming for either
• 44:51 : bigger one or bigger of login
• 44:54 : those are always our best case scenarios
• 44:59 : yeah that makes sense it really does and
• 45:02 : I think I intuitively like was like this
• 45:05 : is way better there's no way this is Big
• 45:07 : O of in but I didn't quite have the um
• 45:10 : sort of the mathematical I'm I'm also
• 45:13 : not
• 45:14 : a great mathematician by any stretch of
• 45:16 : the imagination so I was kind of lacking
• 45:18 : the like but what is it how does this
• 45:20 : quantify so this makes a lot a lot of
• 45:22 : sense
• 45:24 : yeah
• 45:28 : yeah it did and so this will sort of
• 45:33 : near future in a future session yeah
• 45:36 : um first let me ask you
• 45:39 : um do you have any intuition about how
• 45:44 : this is related to trees
• 45:48 : um
• 45:49 : okay in I don't know that I would call
• 45:50 : it intuition I have a guess and it could
• 45:53 : be way way wrong but I know that
• 45:57 : well I'm guessing that this we use this
• 46:01 : method to find what we're looking for in
• 46:03 : a tree structure that it's going to be
• 46:05 : tied in together because a tree
• 46:06 : structure can be big and has a lot of
• 46:10 : yeah I I don't know dude that's my best
• 46:14 : guess
• 46:15 : yeah there's a mirroring search
• 46:18 : algorithm for binary trees
• 46:20 : and then yeah I think I think you'll see
• 46:23 : the relationship later
• 46:25 : cool
• 46:26 : all right we're doing all right thanks
• 46:28 : Toby I hope you have a great weekend and
• 46:30 : I'll talk to you next week