Programming and Problem Solving with Java

(^550) | Array-Based Lists
Under these conditions, the class hierarchy would look like this:

11.6 Searching

In our SortedListclass, we overrode the insertmethod—the only method that we had to

rewrite to keep the list in sorted order. However, if the list is already sorted, we can perform

a more efficient search. In this section, we look at two searching algorithms that depend on

the list items being in sorted order.

Sequential Search

The isTherealgorithm assumes that the list to be searched is unsorted. A drawback to search-

ing an unsorted list is that we must scan the entire list to discover that the search item is not

present. Think what it would be like if your city telephone book contained people’s names

in random rather than alphabetical order. To look up Marcus Anthony’s phone number, you

would have to start with the first name in the phone book and scan sequentially, page after

page, until you found it. In the worst case, you might examine tens of thousands of names,

only to find out that Marcus’s name is not in the book.

Of course, telephone booksarealphabetized, and the alphabetical ordering makes

searching easier. If Marcus Anthony’s name is not in the book, you can discover this fact

quickly by starting with the A’s and stopping the search as soon as you pass the place where

his name should be. Although the sequential search algorithm inisThereworks in a sorted

list, we can make the algorithm more efficient by taking advantage of the fact that the items

are sorted.

How does searching in a sorted list differ from searching in an unordered list? When

we search for an item in an unsorted list, we won’t discover that the item is missing un-

til we reach the end of the list. If the list is already sorted, we know that an item is miss-

List

UnsortedList SortedList

ListWithSort

T

E

A

M

F

L

Y

Team-Fly®