Chapter 7 SEARCHING 1 Introduction, Notation 2. Sequential Search 3. Binary Search 4. Comparison Trees 5. Lower Bounds 6. Asymptotic 7. Pointers and Pitfalls
Chapter 7 SEARCHING 1. Introduction, Notation 2. Sequential Search 3. Binary Search 4. Comparison Trees 5. Lower Bounds 6. Asymptotic 7. Pointers and Pitfalls
7.1 search: Introduction and notation We are given a list of records, where each record is associated with one piece of information which we shall call a key. We are given one key called the target, and are asked to search the list to nd the record(s(if any) whose key is the same as the target. There may be more than one record with the same key, or there may be no record with a given key
7.1 search:Introduction and notation ◆We are given a list of records, where each record is associated with one piece of information, which we shall call a key. ◆We are given one key, called the target, and are asked to search the list to nd the record(s) (if any) whose key is the same as the target. ◆There may be more than one record with the same key, or there may be no record with a given key
We often ask how times one key is compared with another during a search. this gives us a good measure of the total amount of work that the algorithm will do. C Internal searching means that all the records are kept in high-speed memory. In external searching most of the records are kept in disk les. We study only internal searching. ◆F。 r now, we consider only contiguous lists of records. We shall consider linked structures in Chapter 10
◆We often ask how times one key is compared with another during a search. This gives us a good measure of the total amount of work that the algorithm will do. ◆Internal searching means that all the records are kept in high-speed memory. In external searching, most of the records are kept in disk les. We study only internal searching. ◆For now, we consider only contiguous lists of records. We shall consider linked structures in Chapter 10
Records and Keys in C++ The records (from a class Record) that are stored in the list being searched generally called the list) must conform to the following minimal standards: Every record is associated to a key of a type or class called Key) Key objects can be compared with the standard operators !=,<,><=,> There is a conversion operation to turn any record into its associated Key
Records and Keys in C++ The records (from a class Record) that are stored in the list being searched (generally called the list) must conform to the following minimal standards: ◆Every Record is associated to a key (of a type or class called Key). ◆Key objects can be compared with the standard operators == , != , <, >, <= , >= . ◆There is a conversion operation to turn any Record into its associated Key
The records (from a class Record) that are stored in the list being searched generally called the list) must conform to the following minimal standards: Every record is associated to a key of a type or class called Key Key objects can be compared with the standard operato『s三,=,<>=,>三, There is a conversion operation to turn any record into its associated Key. C Record objects can be compared to each other or to a Key by first converting the record objects to their
The records (from a class Record) that are stored in the list being searched (generally called the list) must conform to the following minimal standards: ◆Every Record is associated to a key (of a type or class called Key). ◆Key objects can be compared with the standard operators == , != , <, >, <= , >= . ◆There is a conversion operation to turn any Record into its associated Key. ◆Record objects can be compared to each other or to a Key by first converting the Record objects to their