Searching an Array for a Given Entry

Problem statement

To see whether an array contains a particular entry, we use a loop much like the ones we used in the previous lessons. Although those loops cycle through the whole array, the loop we need here should stop as soon as the first occurrence of the desired entry is found in the array. Right now, we do not care whether the entry occurs more than once.

Pseudocode

We will now describe the logic we need for this search by developing a pseudocode solution.

First draft pseudocode

The following pseudocode describes the basic logic of the loop:

while (givenEntry is not found and we have more array elements to check)
{
   if (givenEntry equals the next array entry)
      givenEntry is found in the array
}

This loop terminates under one of two conditions:

• Either givenEntry has been found in the array or
• The entire array has been searched without success.

Refined pseudocode

We can refine the previous pseudocode as follows:

index = 0
while (givenEntry is not found and index < numberOfEntries)
{
   if (givenEntry equals myArray[index])
      givenEntry is found in the array
   else
      index++
}

Final pseudocode

An earlier chapter described how we can use a Boolean variable in such a loop. Let’s use the Boolean variable found to indicate whether we have found givenEntry in the array. Initially, found will be false. If and when we find givenEntry in the array, we will change the value of found to true, and the loop will then terminate. Our pseudocode now looks like this:

index = 0
found = false
while (!found && index < numberOfEntries)
{
   if (givenEntry equals myArray[index])
      found = true
   else
      index++
}

This pseudocode is almost Java code at this point.

The Java solution

To implement the “equals” comparison in the pseudocode, we need to know whether the array’s entries are primitive values or objects. Let’s assume that the entries, as well as givenEntry, are strings. Thus, we must use the String method equals instead of the operator == to make the comparisons. Although we could use a while loop, we have chosen to use a for loop in the following program: