Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 813

Chapter Summary

Searching is the task of attempting to find a particular
target value in a collection or array.

Algorithms are grouped into complexity classes, which are
often described using big-Oh notation such as O ( N ) for a
linear algorithm.

Sorting is the task of arranging the elements of a list or
array into a natural ordering.

Sequential search is an O ( N ) searching algorithm that
looks at every element of a list until it finds the target value.

Java's class libraries contain several methods for
searching and sorting arrays and lists, such as
Arrays.binarySearch and Collections.sort .

Binary search is an O (log N ) searching algorithm that
operates on a sorted dataset and successively eliminates
half of the data until it finds the target element.

A Comparator object describes a customized way to
compare objects, enabling arrays or lists of these objects
to be searched and sorted in many orders.

Selection sort is an O ( N 2 ) sorting algorithm that repeat-
edly finds the smallest unprocessed element of the array
and moves it to the frontmost remaining slot of the array.

Empirical analysis is the technique of running a program
or algorithm to determine its runtime. Algorithm
analysis is the technique of examining an algorithm's
code or pseudocode to make inferences about its
complexity.

Merge sort is an O ( N log N ) sorting algorithm, often
implemented recursively, that successively divides the
input dataset into two halves, recursively sorts the halves,
and then merges the sorted halves into a sorted whole.

Self-Check Problems

Section 13.1: Searching and Sorting in the Java Class Libraries
1. Describe two ways to search an unsorted array of String objects using the Java class libraries.

2. Should you use a sequential or binary search on an array of Point objects?

3. Under what circumstances can the Arrays.binarySearch and Collections.binarySearch methods be used
successfully?
Section 13.2: Program Complexity
4. Approximate the runtimes of the following code fragments, in terms of n :
a. int sum = 0;
int j = 1;
while (j <= n) {
sum++;
j *= 2;

}