Suppose we want to determine whether an array of ints contains some target number. The obvious approach is the one used in the `contains()` method of the ArrayList class (Section 5.3): start at the beginning and examine each element in turn. This algorithm is called linear search. Not surprisingly, it takes linear time in both the worst and average cases.

We can make the algorithm slightly more efficient if we know in advance that the array is sorted. The numbers we encounter during a search increase as we move from left to right across the array. If we ever encounter a number which is larger than the target, we can stop searching. Since all of the remaining numbers must be even larger, the target can't possibly appear later in the array.

The code for this improved linear search is given in Figure 8-1.

Figure 8-1. If the array `data` is already sorted, a linear search can sometimes be stopped early.

1 /** Return true if target appears in the sorted array data. */ 2 public static boolean linearSearch(int[] data, int target) { 3 for (int i = 0; (i < data.length) && (data[i] <= target); i++) { 4 if (data[i] == target) { 5 return true; 6 } 7 } 8 return false; 9 } |

In the worst case, this is no faster than the old version. On average, although the running time is still in Q(n), the number of elements we have to examine in a successful search is reduced by a factor of 2. A formal proof of this is left as Exercise 8.2.

To analyze the average number of passes through the loop on an unsuccessful search, we define an exhaustive set of mutually exclusive events. Let event i be the event that the target, if it were present, would belong right before element i. There is one event for each of the n numbers (events 0 through n 1), plus event n, where the target is larger than anything in the array.

In event n, we have to examine n elements to determine that the target is not present. In events 0 through n 1, we have to examine i + 1 elements. If we assume that the n + 1 events are equally likely, the average number of elements examined is:

Thus, on average, we only have to look at between n/2 and (n/2) + 1 elements.

Exercises

8.1 |
There are n! permutations of a set of n elements. For example, the set {A, B, C} has 3! = 6 permutations: ABC, ACB, BAC, BCA, CAB, and CBA. There are (n + 1)! permutations of the set after we add a new target. Argue that, if each of these permutations is equally likely, each of the n + 1 places where the target might belong is equally likely. |

8.2 |
Analyze the average time for a successful linear search. |

## Binary Search |

Part I: Object-Oriented Programming

Encapsulation

Polymorphism

Inheritance

- Inheritance
- Extending a Class
- The Object Class
- Packages and Access Levels
- Summary
- Vocabulary
- Problems
- Projects

Part II: Linear Structures

Stacks and Queues

- Stacks and Queues
- The Stack Interface
- The Call Stack
- Exceptions
- The Queue Interface
- Summary
- Vocabulary
- Problems
- Projects

Array-Based Structures

- Array-Based Structures
- Shrinking and Stretching Arrays
- Implementing Stacks and Queues
- The List Interface
- Iterators
- The Java Collections Framework: A First Look
- Summary
- Vocabulary
- Problems
- Projects

Linked Structures

- Linked Structures
- List Nodes
- Stacks and Queues
- The LinkedList Class
- The Java Collections Framework Revisited
- Summary
- Vocabulary
- Problems
- Projects

Part III: Algorithms

Analysis of Algorithms

- Analysis of Algorithms
- Timing
- Asymptotic Notation
- Counting Steps
- Best, Worst, and Average Case
- Amortized Analysis
- Summary
- Vocabulary
- Problems
- Projects

Searching and Sorting

- Searching and Sorting
- Linear Search
- Binary Search
- Insertion Sort
- The Comparable Interface
- Sorting Linked Lists
- Summary
- Vocabulary
- Problems
- Projects

Recursion

- Recursion
- Thinking Recursively
- Analyzing Recursive Algorithms
- Merge Sort
- Quicksort
- Avoiding Recursion
- Summary
- Vocabulary
- Problems
- Projects

Part IV: Trees and Sets

Trees

Sets

- Sets
- The Set Interface
- Ordered Lists
- Binary Search Trees
- Hash Tables
- The Java Collections Framework Again
- Summary
- Vocabulary
- Problems
- Projects

Part V: Advanced Topics

Advanced Linear Structures

- Advanced Linear Structures
- Bit Vectors
- Sparse Arrays
- Contiguous Representation of Multidimensional Arrays
- Advanced Searching and Sorting
- Summary
- Vocabulary
- Problems
- Projects

Strings

Advanced Trees

- Advanced Trees
- Heaps
- Disjoint Set Clusters
- Digital Search Trees
- Red-Black Trees
- Summary
- Vocabulary
- Problems
- Projects

Graphs

- Graphs
- Terminology
- Representation
- Graph Traversal
- Topological Sorting
- Shortest Paths
- Minimum Spanning Trees
- Summary
- Vocabulary
- Problems
- Projects

Memory Management

Out to the Disk

- Out to the Disk
- Interacting with Files
- Compression
- External Sorting
- B-Trees
- Summary
- Vocabulary
- Problems
- Projects

Part VI: Appendices

A. Review of Java

- A. Review of Java
- A.1. The First Program
- A.2. Variables and Types
- A.3. Loops
- A.4. Interacting with the User
- A.5. Branching
- A.6. Methods and Breaking Out
- A.7. Constants
- A.8. Operators
- A.9. Debugging
- A.10. Coding Conventions

B. Unified Modeling Language

C. Summation Formulae

- C. Summation Formulae
- C.1. Sum Notation
- C.2. Sum of Constants
- C.3. Sum of First n Integers
- C.4. Sums of Halves and Doubles
- C.5. Upper Limit on Sum of a Function
- C.6. Constant Factors

D. Further Reading

Index

Data Structures and Algorithms in Java

ISBN: 0131469142

EAN: 2147483647

EAN: 2147483647

Year: 2004

Pages: 216

Pages: 216

Authors: Peter Drake

Flylib.com © 2008-2020.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net