Data Persistency - Java 2 Micro Edition Application Development - page 139

}
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 is applied again. Step by step, the number of records in question is reduced by half. So,
compared to a linear search, the overall number of comparisons is reduced to a logarithmic
function. For 100 records, a linear search requires 100 comparisons in the worst case and 50 in the
average case; a binary search requires only 7 comparisons. This factor increases with larger
number of records.
The record enumeration does not provide any means to jump over half of the records and go to the
middle. If fast searching in ordered sets of records is important for your application, consider
sorting the whole record store and performing a binary search instead of iterating record
enumerations. In Chapter 9 , "Advanced Application: Blood Sugar Log," we will present the
corresponding algorithms.
Summary
In this chapter you learned about persistent storage of application data. You now know how to use
the methods of the class RecordStore for basic access to the RMS. You know how to convert
custom classes to byte arrays and back and how to iterate, filter, and order record stores using
enumerators.
The next chapter explains how to make connections to other devices or the Internet using the
generic connection framework.