How and Why of Binary Search

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: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