数据结构与程序设计(19) 课件

5/28/2023数据结构与程序设计1数据结构与程序设计(19)5/28/2023数据结构与程序设计2BinarySearch

TheForgetfulVersionofBinarySearch

ForgetthepossibilitythattheKeytargetmightbefoundquicklyandcontinue,whethertargethasbeenfoundornot,tosubdividethelistuntilwhatremainshaslength1.5/28/2023数据结构与程序设计3BinarySearch

TheForgetfulVersionofBinarySearch

Idea:Insearchinganorderedlist,firstcomparethetargettothekeyinthecenterofthelist.Ifitissmaller,restrictthesearchtothelefthalf;otherwiserestrictthesearchtotherighthalf,andrepeat.Inthisway,ateachstepwereducethelengthofthelisttobesearchedbyhalf.Keeptwoindices,topandbottom,thatwillbracketthepartoftheliststilltobesearched.Thetargetkey,provideditispresent,willbefoundbetweentheindicesbottomandtop,inclusive.5/28/2023数据结构与程序设计4BinarySearch

TheForgetfulVersionofBinarySearchInitialization:Setbottom=0;top=the_list.size()−1;ComparetargetwiththeRecordatthemidpoint,mid=(bottom+top)/2;Changetheappropriateindextoporbottomtorestrictthesearchtotheappropriatehalfofthelist.Loopterminateswhentop<=bottom,ifithasnotterminatedearlierbyfindingthetarget.Makeprogresstowardterminationbyensuringthatthenumberofitemsremainingtobesearched,top−bottom+1,strictlydecreasesateachiterationoftheprocess.5/28/2023数据结构与程序设计5TheForgetfulVersionofBinarySearchP282Error_coderecursive_binary_1(constOrdered_list&the_list,constKey&target,intbottom,inttop,int&position){ Recorddata; if(bottom<top){//Listhasmorethanoneentry. intmid=(bottom+top)/2; the_list.retrieve(mid,data); if(target>data)//Reducetotophalfoflist. returnrecursive_binary_1(the_list,target,mid+1,top,position); else//Reducetobottomhalfoflist. returnrecursive_binary_1(the_list,target,bottom,mid,position); } elseif(top<bottom)//Canberemarked? returnnot_present;//Listisempty. else{//Listhasexactlyoneentry. position=bottom; the_list.retrieve(bottom,data); if(data==target)returnsuccess; elsereturnnot_present; }}5/28/2023数据结构与程序设计6TheForgetfulVersionofBinarySearchP283Error_codebinary_search_1(constOrdered_list&the_list,constKey&target,int&position){ Recorddata; intbottom=0,top=the_list.size()-1; while(bottom<top){ intmid=(bottom+top)/2; the_list.retrieve(mid,data); if(data<target) bottom=mid+1; else top=mid; } if(top<bottom)returnnot_present; else{ position=bottom; the_list.retrieve(bottom,data); if(data==target)returnsuccess; elsereturnnot_present; }}5/28/2023数据结构与程序设计7BinarySearch(RecognizingEquality)Examinestheelementinthemiddleofthearray.Isitthesoughtitem?Ifso,stopsearching.Isthemiddleelementtoosmall?Thenstartlookinginsecondhalfofarray.Isthemiddleelementtoolarge?Thenbeginlookinginfirsthalfofthearray.Repeattheprocessinthehalfofthedatathatshouldbeexaminednext.Stopwhenitemisfound,orwhenthereisnowhereelsetolookanditemhasnotbeenfound.5/28/2023数据结构与程序设计8TraceofBinarySearch

data[0][1][2][3][4][5][6][7][8][9]1526385762788491108119item=84

firstmiddlelastdata[0][1][2][3][4][5][6][7][8][9]1526385762788491108119

firstmiddlelastitem>data[middle] first=middle+1

item<data[middle] last=middle-15/28/2023数据结构与程序设计9Tracecontinued

data[0][1][2][3][4][5][6][7][8][9]1526385762788491108119item=84

first,last,middledata[0][1][2][3][4][5][6][7][8][9]1526385762788491108119

first,lastmiddleitem==data[middle] found=trueitem>data[middle] first=middle+15/28/2023数据结构与程序设计10AnotherBinarySearchTrace

data[0][1][2][3][4][5][6][7][8][9]1526385762788491108119item=45

firstmiddlelastdata[0][1][2][3][4][5][6][7][8][9]1526385762788491108119firstmiddlelast

item<data[middle] last=middle-1item>data[middle] first=middle+15/28/2023数据结构与程序设计11Tracecontinued

data[0][1][2][3][4][5][6][7][8][9]1526385762788491108119item=45

first,middle,lastdata[0][1][2][3][4][5][6][7][8][9]1526385762788491108119

first,lastmiddleitem<data[middle]

last=middle-1item>data[middle]

first=middle+15/28/2023数据结构与程序设计12Traceconcludes

data[0][1][2][3][4][5][6][7][8][9]1526385762788491108119item=45

lastfirst

first>last

found=false5/28/2023数据结构与程序设计13BinarySearchRecognizingEqualityP284Error_coderecursive_binary_2(constOrdered_list&the_list,constKey&target,intbottom,inttop,int&position){ Recorddata; if(bottom<=top){ intmid=(bottom+top)/2; the_list.retrieve(mid,data); if(data==target){ position=mid; returnsuccess; } elseif(data<target) returnrecursive_binary_2(the_list,target,mid+1,top,position); else returnrecursive_binary_2(the_list,target,bottom,mid-1,position); } elsereturnnot_present;}5/28/2023数据结构与程序设计14BinarySearchRecognizingEqualityError_codebinary_search_2(constOrdered_list&the_list,constKey&target,int&position)/*Post:IfaRecordinthelisthaskeyequaltotarget,thenpositionlocatesonesuchentryandacodeofsuccessisreturned.Otherwise,notpresentisreturnedandpositionisundefined.Uses:MethodsforclassesOrdered_listandRecord.*/{ Recorddata; intbottom=0,top=the_list.size()-1; while(bottom<=top){ position=(bottom+top)/2; the_list.retrieve(position,data); if(data==target)returnsuccess; if(data<target)bottom=position+1; elsetop=position-1; } returnnot_present;}5/28/2023数据结构与程序设计15BinarySearch--Mainvoidmain(){ Keytarget(5); Ordered_listmylist; for(inti=0;i<10;i++)mylist.insert(Record(i,10)); cout<<"Theorderedlistis:"<<endl; mylist.traverse(print); cout<<endl<<"Thetargetis:"<<target.the_key()<<endl; intbottom=0; inttop=mylist.size()-1; intposition=-1;

cout<<endl<<"Userecursive_binary_1Method:"<<endl; if(recursive_binary_1(mylist,target,bottom,top,position)==success) cout<<"Getthetargetinposition:"<<position<<endl; else cout<<"Targetnotpresent."<<endl;5/28/2023数据结构与程序设计16ResultTheorderedlistis:0123456789Thetargetis:5Userecursive_binary_1Method:Getthetargetinposition:55/28/2023数据结构与程序设计17BinarySearch--Main position=-1; cout<<endl<<"Usebinary_search_1Method:"<<endl; if(binary_search_1(mylist,target,position)==success) cout<<"Getthetargetinposition:"<<position<<endl; else cout<<"Targetnotpresent."<<endl;5/28/2023数据结构与程序设计18BinarySearch--Main

cout<<endl<<"Userecursive_bin