Sequential Search of Unsorted Array in Java

Let’s imagine we have mountain climbers. They are climbing Mount Sobo and can be at a unique height along this mountain. Let’s say there are five locations at which there exist fauna at any given time. These positions along the height axis are chosen at random. If you then type the correct randomly-selected height, you will have found fauna.

This is how we set up the MountSobo class with two array instance variables:

  • An array of ints that holds the heights which are populated with fauna sought
  • An array of Strings that holds the corresponding fauna

Both arrays have five elements and there is a one-to-one correspondence between the two arrays. The populated location #1 will have fauna #1,  populated location #2 will have fauna #2, and so on. This programming technique is called parallel arrays.

We fill the populated heights array with heights chosen randomly from entries. We fill the fauna array with Strings representing fauna descriptions. When we enter a climber’s height along the mountain, we can look through the populated heights array for the climber’s position. If the climber’s position up the mountain is in the populated heights array, you use its array index in the fauna array to retrieve the fauna that the climber found. If the height was not found in the array, you know the climber is not in a position where fauna currently are.

Here is the MountSobo class:

Screen Shot 2018-07-16 at 7.54.42 AM.pngScreen Shot 2018-07-16 at 7.55.29 AM.pngScreen Shot 2018-07-16 at 7.55.56 AM.png

The constructor randomly generates values to fill the array by calling the utility method, fillPopulatedheights (lines 25–32). The fillPopulatedheights method does not necessarily generate different numbers; however, the likelihood of two numbers indicating the populated position being equal is very small. We declare the fillPopulatedheights method as private because it is designed to be called only by the methods of this class. The indexOfHeight method (lines 52–60) performs a Sequential Search, which compares the climber’s position up the mountain to each element in the array one by one. The indexOfHeight method accepts a parameter, travelerHeight, which is searched for in the array. If travelerHeight is found, indexOfHeight returns the index of that array element. If travelerHeight is not found, that is, if none of the elements in the array matches the value of travelerHeight, indexOfHeight returns −1. Since −1 is not a valid array index, it’s a good value to use to indicate that the search was unsuccessful. Notice that if the current array element matches the travelerHeight, the indexOfHeight method returns immediately to the caller (line 57); that is, the method stops executing. The return value is the index of the element that matched travelerHeight. If, however, the method finishes executing all iterations of the for loop, then the method has looked at every element in the array without finding a match. In that case, the method returns −1 (line 59), indicating that travelerHeight was not found. Our getFauna method (lines 39–46) calls indexOfHeight to check if its travelerHeight parameter is a winning number; if it is, it uses the array index returned by indexOfHeight in order to return the corresponding element of the array fauna (line 45).

Here is a client application that uses our MountSobo class:

Screen Shot 2018-07-15 at 10.01.28 PM.pngScreen Shot 2018-07-15 at 10.01.47 PM.png

We instantiate a MountSobo object reference named inhabitedHeights (line 14). We then prompt for a traveler’s height up the mountain (lines 17–19) and call the getFauna method (line 25) in order to output any fauna that may have been found at the current height.

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s