Cơ sở dữ liệu - Chapter 5: Searching

Nội dung text: Cơ sở dữ liệu - Chapter 5: Searching

1. Chapter 5 - Searching Sequential Search . In an unordered list . In an ordered list Binary Search . Forgetful Version . Recognizing Equality . Comparison Tree Linked List vs. Contiguous List 1
2. Searching . We are given a list of records. Each record is associated with a key. . We are given one key (target), and are asked to search the list to find the record(s) whose key is the same as the target. . May be more than one record with the same key. . May be no record with a given key. 2
3. Searching . We often asked how many times one key is compared with another during a search. . Internal searching: all records are kept in the high-speed memory. . External searching: most of the records are kept in disk files. 3
4. Sequential Search Begin at one end of the list and scan down until the desired key is found or the other end is reached 4
5. Contiguous List count n 0 1 2 3 n-2 n-1 max-2 max-1 max data x x x x x x General DataType: List DataType key count field1 field2 data > End List fieldn End DataType 5
6. Sequential Search in an unordered list ErrorCode Sequential_Search_1(val target , ref position ) Searches the list to find the record whose key is the same as the target Post If an entry in the list has key equal to target, then return found and position locates such an entry within the list. Otherwise return notFound and position becomes invalid. 1. position = 0 2. loop (position < number of elements in the list) 1. if (dataposition.key = target) 1. return found 2. position = position + 1 3. return notFound End Sequential_Search_1 6
7. Sequential Search in an unordered list (cont.) 7
8. Sequential Search in an ordered list
9. Sequential Search in an ordered list Sequential_Search_2(val target , ref position ) Searches the list to find the record whose key is the same as the target Pre list is an ordered list. Post If an entry in the list has key equal to target, then return found and position locates such an entry within the list. Otherwise return notFound and position becomes invalid. 1. position = 0 2. loop ( (position <number of elements in the list) AND (dataposition.key <= target) ) 1. if (dataposition.key = target ) 1. return found 2. position = position + 1 3. return notFound End Sequential_Search2 9
10. Binary Search (only in ordered list) IDEA: In searching an ordered list, First compare the target to the key in the center of the list. If it is smaller, restrict the search to the left half; Otherwise restrict the search to the right half, and repeat. In this way, at each step we reduce the length of the list to be searched by half. 10
11. Binary Search (cont.)  The idea of binary search is very simple.  But it is exceedingly easy to program it incorrectly.  The method dates back at least to 1946, but the first version free of errors and unnecessary restrictions seems to have appeared only in 1962!  One study showed that about 90% of professional programmers fail to code binary search correctly, even after working on it for a full hour.  Another study found correct solutions in only five out of twenty textbooks. 11
12. Binary Search Algorithm  Keep two indices, top and bottom, that will bracket the part of the list still to be searched.  The target key, provided it is present, will be found between the indices bottom and top, inclusive.  Initialization: Set bottom = 0; top = the_list.Size() – 1;  Compare target with the Record at the midpoint, mid = (bottom+ top) / 2; // (bottom <= mid < top)  Change the appropriate index top or bottom to restrict the search to the appropriate half of the list. 12
13. Binary Search Algorithm (cont.)  Loop terminates when top <= bottom, if it has not terminated earlier by finding the target.  Make progress toward termination by ensuring that the number of items remaining to be searched, top – bottom + 1, strictly decreases at each iteration of the process. 13
14. The Forgetful Version of Binary Search Forget the possibility that the Key target might be found quickly and continue, whether target has been found or not, to subdivide the list until what remains has length 1. ErrorCode Binary_Search_1 (val target , ref position ) Searches the list to find the record whose key is the same as the target Pre list is an ordered list. Post If an entry in the list has key equal to target, then return found and position locates such an entry within the list. Otherwise return notFound and position becomes invalid. 14
15. The Forgetful Version of Binary Search (cont.) ErrorCode Binary_Search_1 (val target , ref position ) Searches the list to find the record whose key is the same as the target 4. if (top data ) mid 3. else 1. bottom = mid + 1 1. return notFound 3. else 1. top = mid End Binary_Search_1 15
16. The Forgetful Version of Binary Search (cont.)  The division of the list into sublists is described in the following diagram:  Only entries strictly less than target appear in the first part of the list, but the last part contains entries greater than or equal to target.  When the middle part of the list is reduced to size 1, it will be guaranteed to be the first occurrence of the target if it appears more than once in the list. 16
17. The Forgetful Version of Binary Search (cont.)  We must prove carefully that the search makes progress towards termination.  This requires checking the calculations with indices to make sure that the size of the remaining sublist strictly decreases at each iteration.  It is also necessary to check that the comparison of keys corresponds to the division into sublists in the above diagram. 17
18. Recognizing Equality in Binary Search Check at each stage to see if the target has been found. ErrorCode Binary_Search_2 (val target , ref position ) Searches the list to find the record whose key is the same as the target Pre list is an ordered list. Post If an entry in the list has key equal to target, then return found and position locates such an entry within the list. Otherwise return notFound and position becomes invalid. 18
19. Recognizing Equality in Binary Search (cont.) ErrorCode Binary_Search_2 (val target , ref position ) 1. bottom = 0 2. top = number of elements in the list -1 3. loop ( bottom datamid ) 1. bottom = mid + 1 4. else 1. top = mid -1 End Binary_Search_2 19
20. Recognizing Equality in Binary Search (cont.)  The division of the list into sublists is described in the following diagram:  The first part of the list contains only entries strictly less than target, and the last part contains entries strictly greater than target.  If target appears more than once in the list, then the search may return any instance of the target (There's the disadvantage of the second version of binary search). 20
21. Recognizing Equality in Binary Search (cont.)  Proof of progress toward termination is easier than for the first method. 21
22. Binary Search (cont.) 25
23. Numbers of comparisons for average successful searches 26
24. Binary Search in Contiguous Lists OK! 27
25. Binary Search in Linked Lists How to implement dataposition ? . Retrieve? Cost to retrieve element at position p is p Have to re-calculate the cost of the search ! . GetNext? NO: GetNext gets elements in sequential order Two solutions: . Assume that retrieving an element at position p cost 1 Binary search . Use other searching method 28