数据结构与程序设计(王丽苹)19search.ppt
5/27/2023,数据结构与程序设计,1,数据结构与程序设计(19),王丽苹,5/27/2023,数据结构与程序设计,2,Binary SearchThe 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.,5/27/2023,数据结构与程序设计,3,Binary SearchThe Forgetful Version of Binary Search,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.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.,5/27/2023,数据结构与程序设计,4,Binary SearchThe Forgetful Version of Binary Search,Initialization:Set bottom=0;top=the_list.size()1;Compare target with the Record at the midpoint,mid=(bottom+top)/2;Change the appropriate index top or bottom to restrict the search to the appropriate half of the list.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.,5/27/2023,数据结构与程序设计,5,The Forgetful Version of Binary Search P282,Error_code recursive_binary_1(const Ordered_list,5/27/2023,数据结构与程序设计,6,The Forgetful Version of Binary Search P283,Error_code binary_search_1(const Ordered_list,5/27/2023,数据结构与程序设计,7,Binary Search(Recognizing Equality),Examines the element in the middle of the array.Is it the sought item?If so,stop searching.Is the middle element too small?Then start looking in second half of array.Is the middle element too large?Then begin looking in first half of the array.Repeat the process in the half of the data that should be examined next.Stop when item is found,or when there is nowhere else to look and item has not been found.,5/27/2023,数据结构与程序设计,8,Trace of Binary Search,item=84,first middle last,data0 1 2 3 4 5 6 7 8 9,15 26 38 57 62 78 84 91 108 119,first middle last,5/27/2023,数据结构与程序设计,9,Trace continued,item=84,first,last,middle,first,last middle,item=data middle found=true,5/27/2023,数据结构与程序设计,10,Another Binary Search Trace,item=45,first middle last,data0 1 2 3 4 5 6 7 8 9,15 26 38 57 62 78 84 91 108 119,first middle last,5/27/2023,数据结构与程序设计,11,Trace continued,item=45,first,middle,last,5/27/2023,数据结构与程序设计,12,Trace concludes,item=45,last first,5/27/2023,数据结构与程序设计,13,Binary Search Recognizing Equality P284,Error_code recursive_binary_2(const Ordered_list,5/27/2023,数据结构与程序设计,14,Binary Search Recognizing Equality,Error_code binary_search_2(const Ordered_list,5/27/2023,数据结构与程序设计,15,Binary Search-Main,void main()Key target(5);Ordered_list mylist;for(int i=0;i10;i+)mylist.insert(Record(i,10);coutThe ordered list is:endl;mylist.traverse(print);coutendlThe target is:target.the_key()endl;int bottom=0;int top=mylist.size()-1;int position=-1;coutendlUse recursive_binary_1 Method:endl;if(recursive_binary_1(mylist,target,bottom,top,position)=success)coutGet the target in position:position endl;else coutTarget not present.endl;,5/27/2023,数据结构与程序设计,16,Result,The ordered list is:0 1 2 3 4 5 6 7 8 9The target is:5Use recursive_binary_1 Method:Get the target in position:5,5/27/2023,数据结构与程序设计,17,Binary Search-Main,position=-1;coutendlUse binary_search_1 Method:endl;if(binary_search_1(mylist,target,position)=success)coutGet the target in position:position endl;else coutTarget not present.endl;,5/27/2023,数据结构与程序设计,18,Binary Search-Main,coutendlUse recursive_binary_2 Method:endl;if(recursive_binary_2(mylist,target,bottom,top,position)=success)coutGet the target in position:position endl;else coutTarget not present.endl;position=-1;coutendlUse binary_search_2 Method:endl;if(binary_search_2(mylist,target,position)=success)coutGet the target in position:position endl;else coutTarget not present.endl;cin.get();,5/27/2023,数据结构与程序设计,19,Binary Search-Main,目录BinarySearch下例程,5/27/2023,数据结构与程序设计,20,二分法的效率分析,二分法检索每经过一次比较就将检索范围缩小一半，第i次比较可能比较的元素个数如下表 比较次数 可能比较的元素个数 1 1=20 2 2=21 3 4=22 j 2j-1二分法查找的效率近似为 O(log2n),5/27/2023,数据结构与程序设计,21,Homework,BOOK P285 E1,E2,
