Java Reference
In-Depth Information
[59, 97, 34, 90, 79, 56, 24, 51, 30, 69]
Please enter an integer value (-1 to quit):
79
79 was found in position 4
Please enter an integer value (-1 to quit):
61
61 was not found
Please enter an integer value (-1 to quit):
51
51 was found in position 7
Please enter an integer value (-1 to quit):
-1
Fig. 19.2
|
Sequentially searching an array for an item. (Part 2 of 2.)
Method
linearSearch
Method
linearSearch
(lines 10-18) performs the linear search. The method receives as
parameters the array to search (
data
) and the
searchKey
. Lines 13-15 loop through the
elements in the array
data
. Line 14 compares each with
searchKey
. If the values are equal,
line 15 returns the
index
of the element. If there are
duplicate
values in the array, linear
search returns the index of the
first
element in the array that matches the search key. If the
loop ends without finding the value, line 17 returns
-1
.
Method
main
Method
main
(line 20-51) allows the user to search an array. Lines 25-28 create an array
of
10
int
s and populate it with random
int
s from
10
-
99
. Then, line 30 displays the array's
contents using
Arrays
static
method
toString
, which returns a
String
representation
of the array with the elements in square brackets (
[
and]) and separated by commas.
Lines 33-34 prompt the user for and store the search key. Line 39 calls method
lin-
earSearch
to determine whether
searchInt
is in the array
data
. If it's not,
linearSearch
returns
-1
and the program notifies the user (lines 41-42). If
searchInt
is in the array,
linearSearch
returns the position of the element, which the program outputs in lines 44-
45. Lines 48-49 get the next search key from the user.
Searching algorithms all accomplish the
same
goal—finding an element (or elements) that
matches a given search key, if such an element does, in fact, exist. There are, however, a
number of things that differentiate search algorithms from one another.
The major differ-
ence is the amount of effort they require to complete the search.
One way to describe this effort
is with
Big O notation
, which indicates how hard an algorithm may have to work to solve
a problem. For searching and sorting algorithms, this depends particularly on how many
data elements there are. In this chapter, we use Big O to describe the worst-case run times
for various searching and sorting algorithms.
Suppose an algorithm is designed to test whether the first element of an array is equal to
the second. If the array has 10 elements, this algorithm requires one comparison. If the
array has 1000 elements, it still requires one comparison. In fact, the algorithm is com-
pletely independent of the number of elements in the array. This algorithm is said to have
