Searching, Sorting and Big O - Java: How to Program Early Objects - page 812

Chapter Algorithm Location

21 Linear search of a List

Binary tree search

Exercise 21.21
Exercise 21.23

Sorting Algorithms:
16

sort method of class Collections
SortedSet collection

Figs. 16.6-16.9
Fig. 16.17

19 Selection sort

Insertion sort
Recursive merge sort
Bubble sort
Bucket sort
Recursive quicksort

Section 19.6
Section 19.7
Section 19.8
Exercises 19.5 and 19.6
Exercise 19.7
Exercise 19.10

21 Binary tree sort Section 21.7

Fig. 19.1 | Searching and sorting algorithms covered in this text. (Part 2 of 2.)

19.2 Linear Search
Looking up a phone number, finding a website via a search engine and checking the def-
inition of a word in a dictionary all involve searching large amounts of data. This section
and Section 19.4 discuss two common search algorithms—one that's easy to program yet
relatively inefficient (linear search) and one that's relatively efficient but more complex to
program (binary search).

Linear Search Algorithm
The linear search algorithm searches each element in an array sequentially. If the search
key does not match an element in the array, the algorithm tests each element, and when
the end of the array is reached, informs the user that the search key is not present. If the
search key is in the array, the algorithm tests each element until it finds one that matches
the search key and returns the index of that element.
As an example, consider an array containing the following values

34 56 2 10 77 51 93 30 5 52

and a program that's searching for 51. Using the linear search algorithm, the program first
checks whether 34 matches the search key. It does not, so the algorithm checks whether
56 matches the search key. The program continues moving through the array sequentially,
testing 2, then 10, then 77. When the program tests 51, which matches the search key, the
program returns the index 5, which is the location of 51 in the array. If, after checking
every array element, the program determines that the search key does not match any ele-
ment in the array, it returns a sentinel value (e.g., -1 ).

Linear Search Implementation
Class LinearSearchTest (Fig. 19.2) contains static method linearSearch for perform-
ing searches of an int array and main for testing linearSearch .