Hello again, Ed, I tried my idea - and it didn't work. Unfortunately, if you keep the array index sorted, (so the binary search can be used), then there's no advantage, because the index simply matches the subscripts. Meaning that the array would have to be in sorted order, anyway.
Using a double index system might work, but is intuitively repulsive, to me. Maintaining a sorted heap, or the like, sounds much more inviting and elegant, than a double index system with arrays. Still, for any single access system, with less than 5,000 records, I don't see a problem with just keeping the array sorted by a unique integer value, whether it be a student i.d. number, employee number, or whatever. Clearly, that will make for a lot of sorting, but also, I believe an optimized insertion function can make fast work of getting that record into the right array position. Recently, I made a program to test an array searcher. First I made an array with 10,000 subscripts, then populated it with random integers, and got the whole array, sorted. Then a simple search done by going to the middle of the array, and making a comparison was run. Next, depending on the comparison of the middle array value, the program either incremented up, subscript by subscript (or down, subscript by subscript), until it either found the target of the search, or it reached the end of the array. Average search time was less than a second! And I'm using a 3 year old laptop (P3 @ 850Mhz cpu). Searching for strings is a much more time-consuming task, but again, since the first letter of the last name will not match in most cases, the search can by-pass most of the really time-consuming portion of checking string values. I do think it important NOT to sort and be re-sorting the array by strings. Ed, the question was raised about k in your complexity description. Is that some constant, and would you explain it for us? Dave
