SEARCHING AND SORTING - Java Programming: From Problem Analysis to Program Design - page 908

Chapter 9 introduced arrays, a structured data type. Arrays are a convenient way to store
and process data values of the same type. You learned how to use loops effectively with
arrays for input/output, initialization, and other operations. You also learned how to pass
an entire set of values as a single parameter. This chapter continues the discussion of
arrays and shows you how to use them effectively for processing lists.

List Processing
A list is a set of values of the same type. Because all values are of the same type, it is
convenient to store a list in an array, specifically a one-dimensional array. The size of a list
is the number of elements in the list. Because a list's size can increase and decrease, the
array you use to store the list should be declared to be the maximum size of the list.
Some basic operations performed on a list are:
￿ Search the list for a given item.
￿ Sort the list.
￿ Insert an item in the list.
￿ Delete an item from the list.
The following sections discuss algorithms to perform some of these operations.

Searching
Chapter 9 described a sequential search algorithm and also illustrated how to use it. Recall
that the sequential search searches the array sequentially starting from the first array element.
Suppose that you have a list with 1000 elements, as shown in Figure 14-1.

[0] [1] [249] [499] [999]

... ... ... ...

FIGURE 14-1 List of 1000 elements

If the search item is the second item in the list, the sequential search makes two key
comparisons (also called item comparisons) to determine whether the search item is
in the list. Similarly, if the search item is the 900 th item in the list, the sequential search
makes 900 key comparisons to determine whether the search item is in the list. If the
search item is not in the list, the sequential search makes 1000 key comparisons.
If searchItem is always at the end of the list , it will take many comparisons to find
searchItem . Also, if searchItem is not in the list , then we will compare searchItem