Java Reference
In-Depth Information
4.7 A basic application of arrays: Searching **
Consider the following simple search problem encountered very day by in
programmers: We are given a set
,andwe
would like to know whether a given query element
E
belongs to that set or not:
That is mathematically for short,
E
E
of
n
integers
E
=
{
E
1
, ..., E
n
}
?. This search task is essential to decide
whether we should add this element to the set or not. Let the data-structure
for storing the
n
elements of
∈E
be an array named
array
.
The
sequential search
inspects in turn all the array elements
array[i]
and
performs a comparison with the query element
E
to check for equality or not. If
for a given index position
i
the query element matches the array element (that
is, predicate
array[i]==E
is evaluated to
true
) then the element is found and
the index of its position in the array is reported. Otherwise, we need to browse
the full array before answering that
E
was not found in the array. This sequential
search approach is summarized by the following program:
E
Program 4.15
Sequential search: Exhaustive search on arrays
class
SequentialSearch
{
static int
SequentialSearch (
int
[ ]
array ,
int
key)
{
int
i;
for
(i=0;i
<
array . length ; i++)
if
(array [ i]==key)
return
i;
return
−
1;
}
public static void
main ( String [ ]
args )
int
[] v=
{
1,6,9 ,12
,45 , 67, 76, 80, 95
}
;
System . out . println (
"Seeking for element 6: Position "
+
SequentialSearch (v,6) ) ;
System . out . println (
"Seeking for element 80: Position "
+
SequentialSearch (v,80) ) ;
System . out . println (
"Seeking for element 33: Position "
+
SequentialSearch (v,33) ) ;
}
}
Running the program, we get the following output:
Seeking for element 6: Position 1
Seeking for element 80: Position 7
Seeking for element 33: Position -1
For query elements that are not present inside the array, we have to wait to
reach the end of array to return
−
1. This explains why this sequential search is
Search WWH ::
Custom Search