574
for(searchIndex = passCount + 1 ; searchIndex < numItems;
searchIndex++)
if(listItems[searchIndex].compareTo(listItems[minIndex]) < 0 )
minIndex = searchIndex;
temp = listItems[minIndex]; // Swap
listItems[minIndex] = listItems[passCount];
listItems[passCount] = temp;
}
6.Describe how the insertoperation can be used to build a sorted list from
unsorted input data. (pp. 545–548)
7.Describe the basic principle behind the binary search algorithm. (pp. 552–557)Answers
1.A list is a variable-sized structured data type; an array is a built-in type often used to implement a list.
2.No.- index = 0 ;
while(listItems[index].compareTo(item) != 0 )
index++;
for(intcount = index; count < numItems- 1 ; count++)
listItems[count] = listItems[count+ 1 ];
numItems--;
4.The average number is 500.5 iterations. The maximum is 1,000 iterations.5.The only required change is to
replace the < 0 with > 0 in the inner loop. As a matter of style, the name minIndexshould be changed to
maxIndex.6.The list initially has a length of 0. Each time a value is read,insertadds the value to the list in its
correct position. When all the data values have been read, they are in the array in sorted order.7.The binary
search takes advantage of sorted list values, looking at a component in the middle of the list and deciding
whether the search value precedes or follows the midpoint. The search is then repeated on the appropriate
half, quarter, eighth, and so on, of the list until the value is located.
Exam Preparation Exercises
1.A binary search can be applied to integers as well as to objects. Suppose the fol-
lowing values are stored in an array in ascending order:
28 45 97 103 107 162 196 202 257
Applying the binary search algorithm to this array, search for the following val-
ues and indicate how many comparisons are required to either find the
number or find that it is not present in the list.
a. 28
b. 32
c. 196
d. 194