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!

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:49 : ask it
- 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:01 : about this like can't you do it a more
- 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:57 : about
- 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
- 19:59 : uh so you start with
- 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:11 : but actually your your point is valid
- 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:47 : um take your time think about it uh
- 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:54 : think about this when you look at these
- 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:25 : awesome I'm glad that made sense okay
- 45:28 : yeah it did and so this will sort of
- 45:30 : lead into I'm talking about trees in the
- 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