0:01

When keys are comparable and we can put them in order. We saw that we can use

binary search to get an efficient symbol table implementation. But we can also

provide a lot of convenient functionality for the client that's what we are going to

look at next. So this is just an example of an application that might try to

associate keys with values. An illustration of all the different

operations that a client might want. So we already looked at the Get operation so we

might want to know what city is associated with the event that happened at time nine

o'clock, thirteenth and so that should return that value. But there's plenty of

other things that we might want. Like, for example, what's the earliest time? That's

the min or what's the latest time? That's the max. What about, being able to iterate

between, among all the keys between two given times? That, certainly is

convenient. Then there's, what's the seventh largest times, that's select that

like a median, it generalizes min or max? Which key is that, happens second or

seventh? So that's, order statistics, a dynamic thing what happened, whats the

closest time, thing that happened just before, five past nine. Certainly, plenty

of clients might want, want that. So this one is, I've only got ten tickets to sell.

So that's the cut off point for, selling, seven tickets that's the cut off point.

For, anybody after that time doesn't get a ticket. And, and this one might be, if

there's a time cut off. I'm not going to sell tickets to anyone that came after

that time. And then the corresponding one is, what's the first thing that happened

after that time? That's call in to the radio show, I'm going to take that caller,

the first call that comes at nine:30. And so forth. So then see how many things

happen between nine:15 and nine:25. And how many calls were there before

nine:10:25? So you can see that there's, all of these operations are quite natural

when we have the, table in sorted order. And that's what we have for our binary

search implementation. So we can, implement these, efficiently and they are,

convenient and useful for the clients. So typically for ordered simple tables, when

keys are comparable will provide a much wider interface it's very useful for many

clients. So we say that we're dealing with keys that are comparable by simply adding

this extents comparable key to our declaration. Same way we did for sorting

methods. So all that means is that our implementations can use compared to but

for the client it means that all these operations have meaning. Give me the

minimum key, give me the largest key, and then I can get the value associated with

that using that. Give me the largest key less than or equal to this key value or

the smallest key greater than that key value, give me the number of keys less

than that key. You can actually implement priority queues this way. Delete the

minimum key, delete the largest key. Now usually we argue against why the interface

is just adding operations to an interface, usually our reason for doing so is that we

can't guarantee that all the operations can be performing efficiently. In this

case, as we'll see, ultimately we have ways to guarantee that all the operations

can be formed efficiently. And they're so convenient for clients. It's certainly

worth adding them. So we have iterate through all the keys, and iterate through

all the keys in a given range, and count the number of keys in a given range. All

of these operations are very useful for clients and we'll see plenty of examples

later on. So we have to greatly expand our, our table. What, what are going to be

the cost of all of these things. And this is a big difference between the binary

search implementation where the keys are kept in order in an array, in the

sequential search implementation, when they're all in a link list. So, for

example, to provide order and iteration, you have to get them sorted. And that's,

going to be a lot of work, and take N lg N time. Whereas binary search, you just

iterate through, the things in order. The give me the seventh key we just go and

look there, they are in order. Rank operation, that is essentially what binary

search provides. That's the, our basic implementation is providing rank. Floor

and ceiling that's again is an outgrowth of the rank operation. Minimum and maximum

well again those are like select. Their just right there, you look at the first or

the last. To insert or delete however takes linear time. To maintain the sorted

array in dynamic fashion is going to take linear time you have to go through the

whole thing. And so that's really are the key to thinking about what are symbol

table and symbol tables in general. How could we guarantee that all operations are

fast? Binary research is pretty good but that's a major flaw. It can't maintain a

dynamic table efficiently with binary search and that's going to be your focus

in the next lecture