Now, the problem with binary search is, well, not necessarily the problem,
but the situation is that when it's time to insert a new element,
we have to move everything larger over one position, just like an insertion sort.
So if the table has A, E, R, and S, and we have to insert the value C,
then we have to move the E, R, and S over one position to put the C.
And then put the value associated with C.
You'll have to do the same thing in the vals array.
Move all the values associated with those keys over in one position and
put the associated value in.
So this is a trace of what would happen for our trace.
And again, every insertion involves
making a new position by moving all the larger keys over one position.
Do the same thing in the vals array.
[COUGH] And if it's changing the value
associated with a key that's already there, then it's just a matter of
finding where the key is and changing the value at that index.
So from that trace,
it's pretty easy to see what's involved for the code.
And we'll skip that code and
just take a look at the comparison between this elementary implementation for
symbol tables with the sequential search in an unordered list.
So, one thing is we're using a different key interface.
We're taking advantage of the fact that the keys are comparable
to give us an efficient search.
We can do search in worst case, in average case, in time proportional to log N.
That's what binary search provides for us.
And this is a fine data structure for symbol tables where there is,
[COUGH] that are relatively static,
where the values don't change much, and most of the operations are search.
It's hard to beat binary search.
On the other hand, in a dynamic situation where there are a lot of inserts,
this method is going to be problematic, because the cost of its insert is linear.
It's proportional to N over 2.
If you have a huge number of operations and
every one of them is proportional to the symbol table size,
then you're just not going to be able to support huge numbers of keys.
What we want is sufficient implementations of both search and insert.