ObjectStream is not designed for it out of the box, but the exact solution depends on the size of your data + exact requirements.
1) If data is large, and business requirements are expected to evolve - I'd consider a proper database. E.g. mongodb if you'd like to write entire complex objects in one go (and, as the post implies, transactions are not required).
2) If you stick with ObjectOutputStream, then consider your exact file format - data retrieval would depend on that. However, all solutions boil down to loading the data to a java object in memory, and searching there...:
a) For small data, you could keep all data in a java List/Map (or some wrapper model object such as PhoneBook), then read/write it entirely in one go. E.g. on application startup: read the entire PhoneBook from file (or initialize an empty one if file is missing/corrupt). For search: search the PhoneBook object in memory. For update: update the PhoneBook object then write it entirely to file (in override mode).
It goes without saying that one can add optimizations to the in-memory data structure, e.g. some HashMap to speed up the search.
b) There's an optimization to (a) which allows to append just one record at a time without re-writing the entire data, but it only works for append. Not for delete/update:
Appending to an ObjectOutputStream
c) More advanced ideas are discussed in the following link, but IMHO it feels half way to writing your own database...: Object serialization and random access in java