Searching,Introduction and Notation,Key: The value of an data item in a record which can be used to uniquely identify the record. Searching: The procedure of determining the location of the record in a list based on the key of the record equals to a given value.,Introduction and Notation,External Searching The record to be searched are stored external to the computer memory. E. g. in files on disk or tape. Internal Searching The record to be searched are stored entirely within the computer memory. We consider only internal search and contiguous implementation of the list in this chapter.,Searching a contiguous list of records,The record in the contiguous list meet the following conditions: Every record is associated with a key. Keys can be compared for equality or relative ordering. Records can be compared to each other or to keys by first converting records to their associated keys.,Implementation in C+,The searching programs is worked on ADT Record and its associated ADT Key. E.g. every student record can have a key student number. the student no. may have data type integer.,Implementation in C+,Class key /definition of a key class Public: / Add any constructors and methods for key data Private: / add declaration of key data members here. ; / Add overloaded comparison operations for keys bool operator = (const Key ,/Define record Public: operator Key(); / implicit conversion from Record Key. / add any constructors and methods for Record objects Private: / Add data components. ,Parameters of search function,Each searching function will have two input parameters. The list to be searched. Key for which we are searching. The key is always called the target of the search. Returned value has type Error_code. Indicates whether or not the search is successful in finding and entry with the target key. One output parameter. If the search is successful, output parameter called position will locate the target within the list. If the search is unsuccessful, then output parameter will have an undefined value,Sequential Search,Begin the search at one end of the list and scan down it until the desired key is found or other end is reached.,Error_code sequential_search(const List ,Testing,For testing functions, there are at least two members worth calculating: The average number of key comparisons done over many searches. The amount of CPU time required.,Testing,Class Key int key; public: static int comparisons; Key(int x=0); Int the_key() const ;,/ Add overloaded comparison operations for keys bool operator = (const Key ,Void test_search(int searches, List ,/calculate the number of unsuccessful comparison. Key:comparisons=0; Clock.reset(); for(i=0;i”at”found_atendl; Print_out(“Unsuccessful”,clock.elapsed_time(),Key:comparisons,seraches); ,Continue,-1 0 1 3 4 6 8 10 12,5,0 1 2 3 4 5 6 7 8,search,low,mid,high,5,6 8 10 12,5 6 7 8,low,mid,high,6,5,5,low,mid,high,5,-1 0 1 3 4 6 8 10 12,6,0 1 2 3 4 5 6 7 8,Search,low,mid,high,6,6 8 10 12,5 6 7 8,low,mid,high,6,6,5,low,mid,high,6,Analysis of Sequential Search,Use the count of key comparison as the measure of performance not the total run time or others. The statements that appear outside the for loop are done only once and therefore take insignificant computer time -ignored. For each pass through the loop, one key is compared with the target key. Conclusion: Because the best case and the worst case are not appear all the time. The calculation of average comparison time is more useful. The average number of key comparisons done for sequential search is （12+n)/n=(n+1).(half of the total list),Binary Search,Requirement: The key of the list is in order Procedure: Compare the target key with one in the center of the list. Restrict the attention to only the first or second half of the list depending on whether the target key comes before or after the central one.,Ordered List,An ordered list is a list in which each entry contains a key, such that the keys are in order. That is, if entry i comes before entry j in the list, then the key of entry i is less than or equal to the key of entry j.,Class Specification of Ordered_list,The list operations that do not apply, without modification to an ordered list are insert and replace. The overloaded method places an entry into the correct position, determined by the order of the keys. If the list already contains keys equal to the new one being inserted, then the new key will be inserted as the first of those that are equal.,Class Specification of Ordered_list(1),Class Ordered_list: public List Public: Ordered_list(); Error_code insert(const Record ,Class Specification of Ordered_list(2),Error_code Ordered_list:insert(const Record /call super classs insert function. ,Class Specification of Ordered_list(3),Error_code Ordered_list:insert (int position, const Record /call super classs i