Java Notes

Search Overview

Searching through an array (or other data structure) is a very, very common operation. There are many ways to search, differing on the way the data is organized and how much speed is desired.

Searching and sorting are often treated together

Searching and sorting algorithms are often grouped together for several reasons.

Comparing 3 ways - Operators, Comparable, Comparator

Comparisons are at the heart of both searching and sorting. Comparison turns out not to be quite as simple as it first appears to be. There are three ways values can be compared.

Use predefined sorting and searching methods if possible.

Java defines a number of searching and sorting methods. You should always use these in preference to writing your own because the library methods are almost always faster and have been well tested. However, there are times that the predefined methods don't work for your data structures, so it's also good to understand how these algorithms work.

Predefined sorting and searching methods for arrays

See Array Library Methods for a brief description of the static Array.binarySearch() and Array.sort() methods.

Predefined sorting and searching in the Collections classes

See Collections Class for a brief description of the static Collections.binarySearch() and Collections.sort() methods. This also has a brief discussion of data structures classes which are automatically sorted (those based on trees), or which have better than linear search methods (based on trees or hashing).