數據結構與程序設計王麗蘋19search

1、10/22/2021數據結構與程序設計 1數據結構與程序設計數據結構與程序設計(19) (19) 王麗蘋王麗蘋10/22/2021數據結構與程序設計 2binary searchthe forgetful version of binary searchnforget 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.

2、10/22/2021數據結構與程序設計 3binary searchthe forgetful version of binary searchnidea: 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

3、, at each step we reduce the length of the list to be searched by half.nkeep two indices, top and bottom, that will bracket the part of the list still to be searched.nthe target key, provided it is present, will be found between the indices bottom and top, inclusive.10/22/2021數據結構與程序設計 4binary searc

4、hthe forgetful version of binary searchninitialization: set bottom = 0; top = the_list.size( ) 1;ncompare target with the record at the midpoint, mid = (bottom + top)/2;nchange the appropriate index top or bottom to restrict the search to the appropriate half of the list.nloop terminates when top =

5、bottom, if it has not terminated earlier by finding the target.nmake 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.10/22/2021數據結構與程序設計 5the forgetful version of binary search p282nerror_c

6、ode recursive_binary_1(const ordered_list &the_list, const key &target, int bottom, int top, int &position)n nrecord data;nif (bottom data) / reduce to top half of list.nreturn recursive_binary_1(the_list, target, mid + 1, top, position);nelse / reduce to bottom half of list.nreturn recursive_binary

7、_1(the_list, target,bottom, mid, position);nnelse if (top bottom) / can be remarked?nreturn not_present; / list is empty.nelse / list has exactly one entry.nposition = bottom;nthe_list.retrieve(bottom, data);nif (data = target) return success;nelse return not_present;nn10/22/2021數據結構與程序設計 6the forge

8、tful version of binary search p283nerror_code binary_search_1 (const ordered_list &the_list, const key &target, int &position)nnrecord data;nint bottom = 0, top = the_list.size( ) - 1;nwhile (bottom top) nint mid = (bottom + top)/2;nthe_list.retrieve(mid, data);nif (data target)nbottom = mid + 1;nel

9、sentop = mid;nnif (top data middle first = middle + 1 item data middle first = middle + 110/22/2021數據結構與程序設計 10another binary search trace data0 1 2 3 4 5 6 7 8 915 26 38 57 62 78 84 91 108 119 item = 45 first middle lastdata0 1 2 3 4 5 6 7 8 915 26 38 57 62 78 84 91 108 119 first middle last item d

10、ata middle first = middle + 110/22/2021數據結構與程序設計 11trace continued data0 1 2 3 4 5 6 7 8 915 26 38 57 62 78 84 91 108 119 item = 45 first, middle, lastdata0 1 2 3 4 5 6 7 8 915 26 38 57 62 78 84 91 108 119 first, last middle item data middle first = middle + 110/22/2021數據結構與程序設計 12trace concludes da

11、ta0 1 2 3 4 5 6 7 8 915 26 38 57 62 78 84 91 108 119 item = 45 last first first last found = false10/22/2021數據結構與程序設計 13binary search recognizing equality p284nerror_code recursive_binary_2(const ordered_list &the_list, const key &target, int bottom, int top, int &position)nnrecord data;nif (bottom

12、= top) nint mid = (bottom + top)/2;nthe_list.retrieve(mid, data);nif (data = target) nposition = mid;nreturn success;nnelse if (data target)nreturn recursive_binary_2(the_list, target, mid + 1, top, position);nelsenreturn recursive_binary_2(the_list, target, bottom, mid - 1, position);nnelse return

13、not_present;n10/22/2021數據結構與程序設計 14binary search recognizing equalitynerror_code binary_search_2(const ordered_list &the_list, const key &target, int &position)n/* post: if a record in the list has key equal to target , then position locatesnone such entry and a code of success is returned. otherwis

14、e, not present is returned nand position is undefined.nuses: methods for classes ordered_list and record . */nnrecord data;nint bottom = 0, top = the_list.size( ) - 1;nwhile (bottom = top) nposition = (bottom + top)/2;nthe_list.retrieve(position, data);nif (data = target) return success;nif (data ta

15、rget) bottom = position + 1;nelse top = position - 1;n nreturn not_present;n10/22/2021數據結構與程序設計 15binary search - mainnvoid main()nkey target(5);nordered_list mylist;nfor(int i=0; i10; i+) mylist.insert(record(i,10);ncoutthe ordered list is: endl;nmylist.traverse(print);ncoutendlthe target is: targe

16、t.the_key()endl;nint bottom=0;nint top=mylist.size()-1;nint position=-1;nncoutendluse recursive_binary_1 method:endl;nif(recursive_binary_1(mylist, target, bottom, top, position)=success)ncoutget the target in position: position endl;nelse ncouttarget not present.endl;10/22/2021數據結構與程序設計 16resultnth

17、e ordered list is:n0 1 2 3 4 5 6 7 8 9nthe target is: 5nuse recursive_binary_1 method:nget the target in position: 510/22/2021數據結構與程序設計 17binary search - mainnposition=-1;ncoutendluse binary_search_1 method:endl;nif(binary_search_1(mylist, target, position)=success)ncoutget the target in position: p

18、osition endl;nelse ncouttarget not present.endl;10/22/2021數據結構與程序設計 18binary search - mainncoutendluse recursive_binary_2 method:endl;nif(recursive_binary_2(mylist, target, bottom, top, position)=success)ncoutget the target in position: position endl;nelse ncouttarget not present.endl;nposition=-1;ncoutendluse binary_search_2 method:endl;nif(binary_search_2(mylist, target, position)=success)ncoutget the target in position: position endl;nelse nco