Java™ 2 Micro Edition Application Development

The Search Problem

In the previous sections, you learned to sort and filter records in a record store. Obviously, you can search a record by iterating all records until the desired record is found, or just set a filter that filters out all other records.

Unfortunately, this approach requires looking at all records in the worst case and looking at half of the records in the average case. A search on a sorted set of records can be performed much faster by an algorithm called a binary search. The algorithm goes to the middle of the set and determines whether the element searched is greater or smaller than the record in the middle. Thus, the algorithm can decide in which half of the records the searched element is located. For this half, the procedure ...