0:14

So whats our recurrence relation for the worst-case runtime?

Â Well, the worst case is if we don't find an element.

Â So were going to look at T(n) Is equal to T of roughly n over 2 + c.

Â We have a floor there of n over 2 because if n is odd,

Â let's say there are five elements, then the question is:

Â how big is the problem size on the next call.

Â So if we have five elements we're going to either end up looking in the upper half of

Â the array.

Â Those two elements or the lower half of the array, those two elements

Â because we skipped the midpoint.

Â We already checked them.

Â Plus some constant amount of work to add together, to calculate the midpoint.

Â As well as checking the midpoint against the key.

Â And then our base case is when we have an empty array.

Â And that's just a constant amount of time to check.

Â 1:11

So what's the runtime look like?

Â We got our original size n, and we're going to break it down,

Â n over 2, n over 4.

Â All the way down.

Â How many of these problems are there.

Â Well, if we're cutting something in two over and over again.

Â It's going to take log base two such iterations until we get down to 1.

Â So the total here, is actually log base two of n + 1.

Â The amount of work we're doing is c.

Â So at each level, we're doing c work.

Â So the total amount of work if we sum it,

Â is just the sum from i=0 to log base 2 of n of c.

Â 2:08

All right, what's the iterative version look like.

Â The iterative version has the same parameters low, high, and key.

Â And we have a while loop that goes through similar to the base case so

Â in the base case of the recursive version we were stopping if high is less than low.

Â Here, we have a while loop where the while loop stops if high is less than low.

Â We calculate the midpoint and then again check the key.

Â If it matches the element at the midpoint we return the midpoint. Otherwise,

Â if the key is less than

Â the element, we know we're in the first half of the array and so

Â instead of making a new recursive call like we did in the recursive version we have

Â the original array.

Â And we want to look at the first half of it so we're going to change the value of

Â high and that will be mid minus one because we already checked mid.

Â Otherwise, we want to look in the upper half of the array so we move low up.

Â 3:05

If we reach the end of the while loop.

Â That is if we drop out of the while loop because high is less than low.

Â That meant we have nothing more to search.

Â We have an empty array.

Â And therefore, we didn't find the element in the array.

Â We're going to return low minus 1.

Â So the same result as the recursive version.

Â The difference is we won't be using the stack space that

Â the recursive version uses.

Â You remember we talked two videos ago about this real-life example where we had

Â five languages and we were translating words between any two of those languages.

Â The way we had that represented was parallel arrays,

Â so that at any given index, each of the element in the arrays

Â represented words that were the same in all those languages.

Â So for instance, chair in English is at index two, and

Â in Spanish that's silla and in Italian it's sedia.

Â The problem was it took a long time to look, right?

Â We had 50,000 elements in our arrays, and it took like ten seconds for searching,

Â because we had to really search through all of them

Â if it wasn't there, on average, half of them, just 25,000.

Â So one question might be, why didn't we use a sorted array?

Â Right?

Â You could imagine, for instance, sorting these arrays.

Â Here they're sorted.

Â The good part is, it's easy to find a particular word in a particular language.

Â So I can find house in English, for instance, and

Â find what index that is at very quickly, using binary search.

Â The problem is,

Â I no longer have this correspondence, because the order of the words that

Â are sorted in English is different from the order of the words sorted in Spanish.

Â So if I look at chair, for instance, in English, it no longer maps to silla.

Â So instead, if I look at chair and that's to casa.

Â So although we can find a particular word in our source language,

Â we don't know the corresponding word in the target language.

Â So the solution was to try and find some way we could do sorting and yet

Â still preserve this relationship where everything at an index meant

Â the same translated word. The way to do that was an augmented set of arrays.

Â So what we really did was keep these augmented arrays which were

Â pointers back into the original arrays in sorted order.

Â So we're having a kind of level of indirection.

Â So if I look at English for example, the order of the words in English is chair,

Â house, pimple.

Â Well, what order is that in the original array?

Â It is first element 2, and then element 1, and then element 3.

Â So if you want to do a binary search, you can use this sorted array.

Â Whenever you want to look at what an element

Â 5:43

is in that represented sorted array.

Â So for instance, if we looked at the middle element,

Â which in the sorted array is 2, it has the value 1 and that says go find house.

Â So we basically, say house is sort of at element 2 and

Â chair is at element 1 and pimple's at element 3.

Â The Spanish, of course, has different mapping, so

Â in Spanish, the first sorted word happens to be the first word in the array.

Â The second sorted word is the third word in the Spanish array; and

Â the third sorted word, silla, is the second element.

Â 6:23

We had to pay extra space.

Â And there were, of course, not only just English and Spanish sorted but also French,

Â Italian, and German.

Â So, five arrays, extra arrays.

Â Each array,

Â had 50,000 entries in it and what was the size of each element of the array?

Â Well, it represented a number from one to 50,000 that

Â can be represented in 16-bits which is two bytes.

Â So we had 50,000 elements times 2 bytes,

Â that is 100,000 bytes times 5 is 500,000 bytes.

Â So about a half a megabyte, which today is almost nothing.

Â And even then, was certainly doable 20 years ago.

Â 7:00

That's the cost we have in space.

Â What is the benefit that we get.

Â Well, instead of having to do let's say 50,000 look ups in the worst-case.

Â Instead, we have to do log base two of 50,000 lock ups.

Â So log base 2 of 50,000, that's about, let's see, log base of 1,000 is about ten

Â because two to the ten equals 1024, so we have another factor of 50 to go.

Â Log base 2 of 50 is around,

Â let's say six because I know that 2 to the 5th is equal 32, 2 to the 6th equals 64.

Â So, what that means is,

Â we have 16 references we have to do the array instead of 50,000.

Â That's almost a factor of a thousand, so

Â what that ended up meaning is that when the user clicks translate,

Â instead of taking ten seconds, it was what appeared to be instantaneous.

Â It was well under a tenth of a second.

Â