Programming contest!

The prize is a bag-o-marshmallows to whomever can come up with the most efficient way to solve the "Write, efficient code for extracting unique elements from a sorted list" problem.

Apparently everyone else on the web is content to post the question as a possible interview question. Well, I'm not interviewing for anything. I actually need better way to do this. Sure, I have some ideas, but I can't help thinking there is an optimal way to do this (my head keeps going back to the 2 bowling balls being dropped from the building... I can't help thinking there is a logical connection...).

Some quick background so you understand that the half-arsed check-every-item-in-the-array solution is not what I'm looking for. I'm looking for something that minimizes the number of reads I have to do since this algorithm will actually be applied to reading off a file, not an in memory array. I can guarantee you that the list is in order and that I can traverse the list like an array. So we can treat this particular problem like searching an array.

Consider also that I have to read 339,712 records. So think of an array that long with at least 100 duplicates per unique value. The actual number of duplicates per value is of course unknown. I want to avoid reading as many of those duplicates as I can. The one thing in my favor is that I know that they are all in order. Another thing that is clear to me is that I know the high and low values, so I should be able to deduce the maximum number of unique values. Of course you yourself probably saw that too.

Treat this contest like a C++ or VB contest of course. Answers like “SELECT DISTINCT column_name FROM table_name” will be laughed at and will owe me a bag of marshmallows.

Just to give you a head start (since I actually want the darned answer ASAP), I think that since I know the maximum number of unique elements, there must be an optimal number of jumps I can make through the array. I should compare at those jump points and decide whether or not to investigate the areas in-between my jumps based on the comparison result. Just the same as there was an optimal number of floors to skip in the bowling ball problem, I think there is an optimal number of records to skip here. How do I get that value? Following that, what is the most efficient way to search in-between my jumps? Or am I way off?

Please enlighten me and receive a bag of marshmallows in exchange.