Page 422 - Introduction to Programming with Java: A Problem Solving Approach

388 Chapter 10 Arrays and ArrayLists 10.7 Searching an Array
In order to use an array, you need to access its individual elements. If you know the location of the element you’re interested in, then you simply access the element by putting the element’s index inside square brack- ets. But if you don’t know the location of the element, then you need to search for it. For example, suppose you’re writing a program that keeps track of student enrollments for the courses at your school. The program is supposed to be able to add a student, remove a student, view a student’s data, and so on. All of those op- erations require that you first search for the student within a students array (even the add-a-student operation requires a search, to ensure that the student isn’t already in the array). In this section, we present two tech- niques for searching an array.
Sequential Search
If the array is short (has less than about 20 items), the best way to search it is the simplest way: Step through the array sequentially and compare the value at each array element with the searched-for value. When you find a match, do something and return. Here’s a pseudocode description of the sequential-search algorithm:
i←0
while i < number of filled elements
if list[i] equals the searched-for value <do something and stop the loop>
Adapt generic algorithms
to specific situations.
Typically, algorithms are more generic than Java implementations. Part of problem solv- ing is the process of adapting generic algorithms to specific situations. In this case, the “do something” code will be different for different cases. The findStudent method in Figure 10.10 illustrates one implementation of the sequential-search algorithm. This partic-
increment i
Apago PDF Enhancer
ular method might be part of a Course class that implements an academic course. The Course class stores a course’s name, an array of student ids for the students enrolled in the course, and the number of students in the course. The findStudent method searches for a given student id within the student ids array. If the student id is found, it returns the index of the found id. Otherwise, it returns 􏰂1. Note how findStudent’s code matches the sequential-search algorithm’s logic. In particular, note how findStudent implements <dosomethingandstoptheloop>withareturn istatement.Thereturn iimplements“dosomething” by returning the index of the found student id. It implements “stop the loop” by returning from the method and terminating the loop simultaneously.
In examining the findStudent method, you might be asking yourself “What is the practical use for the returned index?” To do anything with an id in the ids array, you need to know the id’s index. If you don’t know the id’s index in advance, the findStudent method finds the id’s index for you. Later in this chapter, you’ll see how to call a search method and use the returned index when sorting an array and when adding a new value to an array. Are you still asking yourself “What is the practical use for the returned 􏰂1 when the id is not found?” The 􏰂1 can be used by the calling module to check for the case of an invalid student id.
Figure 10.11 contains a CourseDriver class which drives Figure 10.10’s Course class. The CourseDriver class is fairly straightforward. It creates an array of student ids, stores the array in a Course object, prompts the user for a particular student id, and then calls findStudent to see whether that particular student is taking the course. To keep things simple, we use an initializer to create the ids