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
associated keys. Examples of the conversion operation: A method of the class Record with the declaration operator Key( const CA constructor for the class Key with declaration Key const Record & C If the classes Key and record are identical, no conversion needs to be defined since any record is automatically a Key. We do not assume that a record has a Key object as a data member, although often it does. We merely assume that the compiler can turn a record into its corresponding ey
associated keys. ◆Examples of the conversion operation: ◆A method of the class Record, with the declaration operator Key( ) const; ◆A constructor for the class Key, with declaration Key(const Record &); ◆If the classes Key and Record are identical, no conversion needs to be defined, since any Record is automatically a Key. ◆We do not assume that a Record has a Key object as a data member, although often it does. We merely assume that the compiler can turn a Record into its corresponding Key
Parameters for Search Functions Each searching function has two input parameters First is the list to be searched Second is the target key for which we are searching. Each searching function will also have an output parameter and a returned value: The returned value has type Error code and indicates whether or not the search is successful in finding an entry with the target key. If the search is successful, then the returned value is success,and the output parameter called position will locate the target within the list
Parameters for Search Functions Each searching function has two input parameters: ◆First is the list to be searched; ◆Second is the target key for which we are searching. Each searching function will also have an output parameter and a returned value: ◆The returned value has type Error_code and indicates whether or not the search is successful in finding an entry with the target key. ◆If the search is successful, then the returned value is success,and the output parameter called position will locate the target within the list
If the search is unsuccessful, then the value not present is returned, and the output parameter may have an undefined vallue or a value that will differ from one method to another. Key Definition in C++ To select existing types as records and keys a client could use type definition statements such as: typedef int Key; typedef int Record; a client can design new classes that display appropriate behavior based on the following skeletons:
◆If the search is unsuccessful, then the value not present is returned,and the output parameter may have an undefined value or a value that will differ from one method to another. Key Definition in C++ To select existing types as records and keys, a client could use type definition statements such as: typedef int Key; typedef int Record; A client can design new classes that display appropriate behavior based on the following skeletons:
Definition of 在本章我们使用的类声明如下 a Key class class Key static data number i public: static int comparisons: 由于只关心查找key Keylint x=o)i key =x; y 不关心 record中的 int the key ( )const i return key; y 其它内容,因此将 Record定义为key Key& operator=(const int x) i key =x; return *this; y private int ke y char other: typedef Key record
class Key { public: static int comparisons; Key(int x=0) { key = x; } int the_key( ) const { return key; } Key& operator=(const int x) { key = x; return *this; } private: int key; char *other; }; 在本章我们使用的类声明如下： Definition of a Key class typedef Key Record; 由于只关心查找key， 不关心Record中的 其它内容，因此将 Record定义为key static data number
7.2 Sequential Search 1. Algorithm and procedure Begin at one end of the list and scan down it until the desired key is found or the other end is reached: 我们在第6章中实现的fnd方法: int Find(const List entry &x); ∥/查找元素x,找不到返回-1,否则为x在表中的位置 就是顺序查找方法,与本节书上的方法区别仅仅是: 返回了类型是 Error code,位置由引用参数带回
7.2 Sequential Search 1. Algorithm and procedure Begin at one end of the list and scan down it until the desired key is found or the other end is reached: 我们在第6章中实现的find方法： int Find(const List_entry &x); // 查找元素x,找不到返回-1，否则为x在表中的位置 就是顺序查找方法，与本节书上的方法区别仅仅是： 返回了类型是Error_code，位置由引用参数带回