Video 2-5: §2.4 Binary seach

0:00 <Untitled Chapter 1>

0:03 Binary Search Trees

0:03 in this next subsection i want to talk about binary search trees it's clearly one of my favorite data structures because it's so versatile and so ubiquitous in computer science i think almost all programming libraries have a good implementation of it i think python might be the only exception i know of um it's it's a very useful technique it's useful in practice has lots of applications but it's also beautiful in the theory and there's lots of interesting research questions that are still widely open around binary search trees it's clearly a fascinating topic so i'm i'm happy to crack into it again many of you will have seen this before so i will focus a little bit i'll give a very brief introduction to the basics but then focus a little bit on the more advanced comments that i want to make that sometimes are lost in a crowded undergraduate data structures class but uh before we come to this i want to ask you a little question on the side um i haven't prepared this

0:51 Introduction

1:19 on sliders let me just add that okay you should be able to see it now and uh we can leave this open it's just uh this will be about the the terminology of of things and um i want to make sure i'm not talking about things that make absolutely no no sense at la uh to you so what i mean by physical dictionary is is a book i i don't even have one here i like most of my books are in my office locked up safely on campus without any way for me to access them i do have some physical dictionaries maybe i have an a longman english dictionary somewhere downstairs not even sure about that maybe even that's on on campus okay so most people seem to have uh used these and you still know what these look like um that's good because that's a typical metaphor that's um that's used in in this context

2:47 um yeah let's let's continue with this one so i want to see um many of you have said they've seen binary search trees before um but i want to see uh how how well that's stuck

3:09 is there a way to jump to the uh i have to like this briefly i will not i don't want to show the answer right now i want to give you a little more time for this

3:23 The Symbol Table Abstract Data Type

3:23 i want to talk while you're voting i want to talk about the symbol table abstract data type this has many names it's called well symbol table obviously but it's also called a dictionary that's why i asked uh this question that's what this picture is from uh a physical printed dictionary in the classical sense of uh showing well showing explaining words in one language or translating it to another language uh you have these um entries that are uh well usually in alphabetical order right and then you can look up what's the meaning of a word and it's it's exactly that sense that a symbol table represents as well sometimes also called a map that's the name for the interface in java an associative array is the same thing just a slightly different syntax and a key value store is also essentially the same the same thing maybe more from the perspective of a database

4:28 Operations of a Symbol Table

4:29 um the operations of a symbol table i again i take the terminology so that it's consistent with uh the book and videos of of cedric and wayne um but this is also uh how it's called in java so we have an operation put and it gets a key and a value and it just assigns it puts this key value pair into the table which means it assigns the value v to the key k we can also get back the value by this get function so you give it a key and then it returns you the value that was associated with this key earlier on if there is one and you can delete a key well you can delete the key value pair associated with this key and you can check whether a certain key is in the dictionary

5:22 all right a few other small things you can check if it's empty you can check the size you can create an empty one these are all easy to do and not so very not so interesting so i won't discuss these in detail i want to stress that binary search trees or symbol tables in specific uh here we're talking about the abstract data type so i'm sorry i should say the symbol table is really the most fundamental building block in computer science there's so much so many parts in programming that are solved by this and here really every programming library has some symbol table i don't know any like any used programming language that doesn't have a symbol table not all do it by binary search trees but almost all do and there's a good reason for that okay um let me briefly revisit the the question here so uh here you see that most of you um get this right that's exactly what a binary search tree is like so um i can move on with that um a little a little faster than for the heaps maybe

6:36 i want to comment a little bit on on this name symbol tables look very much like mathematical functions and in particular the name map uh suggests this the this analogy

6:53 uh much more they're indeed similar the key difference is that a mathematical function is a static object that never changes if you change the mapping in a mathematical function then it's not really the the same function anymore it's a different function it's um a fixed object it's immutable it's a value if you want whereas simple tables we think of them as a dynamic mapping you can change this mapping over time and you can explicitly remove and insert keys right that's the that's the key distinction

7:32 now let's look at a few very simple ideas for implementing a symbol table and you've seen this kind of dichotomy before so not not too much detail we can use an unordered linked list that's great for put at least if we just append it at the end so you can just add a new key value pair at the end of the list and that's it but if you want to find a key again there's nothing you can do but just scanning linearly through the entire linked list and that's slow so you can do this but it's almost never useful you could think um if unordered is not good maybe we can sort the linked list now i stress linked here and we'll i'll come back to it in a second well if you sort a linked list that's actually totally useless because um now get still is linear time because you can't find you can't access elements faster and put now you have to maintain this sorted order so you have to walk through the list and find the right insertion spot so it looks like ordering the dictionary is not at all useful here that's a bit against our intuition but of course you will probably know this this is not quite true sorting keeping the dictionary sorted

9:06 does help but only if we have an array why does it help well if we have an array we can search with binary search so a quick reminder how binary search works here's an array with numbers sorted ascendingly and we try to find a nice number 69 we start with l and r that's the range of the array that we still have to look into and initially that's just the entire array and we compute the middle between those two now there's a tie could have been either of the two but to make the example interesting let's suppose you always round down the middle to towards the left now you at this step you compare

9:18 How Binary Search Works

10:05 63 with the element that you're looking for and obviously 63 is smaller that means all of the elements on the left here they're also smaller so i can ignore all these elements with a single comparison and that's the magic of a sorted list you can do a single comparison in the middle and then you know for half of the list that the element's not there that's that's pretty good so um we do this and then the range that we still have to look at uh shrinks like this we do the same thing again we compute the middle we compare the middle 80 with the element we're looking for and obviously 80 is too big so we can exclude all this part as well and we're left with this smaller window now we do it one more time oh dear now i jumped all the way back okay bear with me for a second

11:15 should make shorter chapters i guess still heap okay there we are jump jump jump um so we do it one more time compute the middle between those three 77 still too big so we can exclude all these guys well and all the others but they were already out of the game and so we're left with the 67 uh 69 i'm sorry and so the last comparison is to compare these two elements and then we found the element that's um that's binary search i'm sure that you will have seen this before but just in case i wanted to remind you again and

12:10 the key insight in binary search is whenever we do one step one comparison with this middle element we cut the remaining list in half well plus minus one because of the rounding but let's not be too strict about this here what you can show if you take all the rounding into account is uh there's an exact upper bound of um binary logarithm of n rounded down but plus one because sometimes you have a little bit of an around off so you get into a slightly larger list that's the number of comparisons in the worst case to find whether an element is in the list and return its position or find that an element is not in the list and return the position where it should be if it was in the list the key thing i want to stress that here again is you need random access if you don't have an array you're pretty much out of luck with binary search you need to be able to jump into the middle to make this uh efficient comparison there if you cannot do this then binary search is no help you can't implement it and the sorted linked list that we discussed on the slide before doesn't provide this random access okay long long part long long introduction

13:35 finally it's time to introduce the stars of the show today the binary search trees and i like i like this like this way of motivating them we've seen a sorted linked list is almost useless because it doesn't provide a way to access elements efficiently but once we have the position where we are we can very easily add a new element into the list we just splice a new element into the linked chain on the other side a sorted array was great for searching in the static case when the dictionary is fixed it was great to find elements efficiently we could use binary search but if you wanted to insert an element at some point well it's an array so you have to copy everything over and move move the element in and that's again slow so binary search trees are really the solution to make take the best of both worlds a linked representation that allows inserting at any point in time but at the same time allow the access of a of an array to jump into the middle that's that's the essence of of a binary search tree

14:56 [Music] um yeah so i wonder if we should uh do this question here before we move on i probably should have presented this uh along with this slide so let's uh let's just do this uh for a second to see if binary search is clear enough for you guys and then we can move on uh so same game as we've just had it suppose we have an array of numbers and it's just the numbers 10 20 30 40 50 60 70 to make life a little more convenient and you're looking for key 25 what is the sequence of comparisons that the algorithm that i just sketched uh would do and maybe it helps you if i uh show this show this algorithm again

16:31 maybe one more minutes 20 people have voted 23. okay 28 getting closer we had up to 36 in the previous questions so maybe i'll as i said before this unit is really tough for me because i'm i'm jumping back and forth between trying to recap everything that i think a computer scientist should know but also not boring the hell out of those who've seen this before okay 37 is pretty good um let's uh show the results and the vast majority get this right um that's exactly what happens so we we jump into the middle [Music] the middle between in this list is exactly 40s there's no rounding happening so that's there's no

17:36 Results

17:59 no ambiguity in the question so you compare 40 with 25 obviously that's too big so you jump into the lower half so that's just uh these three numbers that are in in the in your list the next comparison is with 20. that's too small so the only remaining list is 30 but you need this last comparison as opposed to the last answer because you have to check whether 25 is in the list when or not now you reduce this to a single element list but you still have to do the check if that single element list contains the 25 or something else like in this case good okay thanks for voting um hope that wasn't too boring good so that was that was binary search