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
