《数据结构与程序设计（王丽苹）19 search.ppt》由会员分享，可在线阅读，更多相关《数据结构与程序设计（王丽苹）19 search.ppt（21页珍藏版）》请在三一文库上搜索。
1、4/16/2020,数据结构与程序设计,1,数据结构与程序设计(19),王丽苹 ,梗秦逸章间锨滨伪有浊代派经封磷秉仕机闲耗趣署比薄润碗温杭冒瑰路藻数据结构与程序设计（王丽苹）19 search数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序设计,2,Binary Search The Forgetful Version of Binary Search,Forget the possibility that the Key target might be found quickly and continue, whether target has been f
2、ound or not, to subdivide the list until what remains has length 1.,松章女晦霞诚抬吸走妖攒硅茶食遍裸桂芦狠管包鸟荒萄淌绍窄膝凡奸猫娶数据结构与程序设计（王丽苹）19 search数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序设计,3,Binary Search The Forgetful Version of Binary Search,Idea: In searching an ordered list, first compare the target to the key in the
3、 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
4、to be searched. The target key, provided it is present, will be found between the indices bottom and top, inclusive.,玻禽咀瞥甘翌胜粘锚夸完纠取稽层将急虱缓芦惨淡鼎菊纲疼购夯史甭回笛数据结构与程序设计（王丽苹）19 search数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序设计,4,Binary Search The Forgetful Version of Binary Search,Initialization: Set bottom =
5、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
6、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.,涯厚容汤麓著的绵杯觅殿潍睬渊教跌疚磅瘩驭徒跺恶皂僳吐洽英券铣哇座数据结构与程序设计（王丽苹）19 search数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序设计,5,The Forgetful Version of Binary Search
7、P282,Error_code recursive_binary_1(const Ordered_list ,寸耐快缘珊蚀傻酚慑翁扳婴漳陇躬盐扣捌鹏非讼做趣伤残淘燕娜彝拧襟籽数据结构与程序设计（王丽苹）19 search数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序设计,6,The Forgetful Version of Binary Search P283,Error_code binary_search_1 (const Ordered_list ,帘校戈卒坡闲迢吏汀揍亢输促脓奖察氖乃观够您巴印他策豪雍当末在瑚滥数据结构与程序设计（王丽苹）19 sea
8、rch数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序设计,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 beg
9、in 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.,生伎验擦升近扮浩姓疽歹纵德毙翌则仕编萌胚侨泉沼褂绕劈粱午舟肝椭渺数据结构与程序设计（王丽苹）19 search数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序
10、设计,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,参贾特云扳蔗霍拓聪犹圾聊嘶腆抚寓针八灌肖矛皱建搂亿靖恕漠兵由遥幅数据结构与程序设计（王丽苹）19 search数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序设计,9,Trace continued,item = 84,first, last, middle,first, last middle,item
11、 = data middle found = true,硒拖壹旧蜀直帚辟艳摆诉靳霍澜信锻眨智禁纷葫穷崩读雍却白躬请庚应杉数据结构与程序设计（王丽苹）19 search数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序设计,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,讼国哇候律捐承愈苔酪销旅像言痛顺技翟炊群板巫肝皑庸猴湿腻彬遏香锤数据结构与程序设
12、计（王丽苹）19 search数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序设计,11,Trace continued,item = 45,first, middle, last,童领玖椅颅磨阁导焰氏振糯锨亩蹭陆刃学贝淘离垦翘暖腕宝曹剪确苞眼伶数据结构与程序设计（王丽苹）19 search数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序设计,12,Trace concludes,item = 45,last first,蚀菱报很蔼钞茫瓤用谋巳裹氟蚂烽完据夷邦崔汕丙虐镭肉蔡垂卜痔抹伤粮数据结构与程序设计（王丽苹）19 sear
13、ch数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序设计,13,Binary Search Recognizing Equality P284,Error_code recursive_binary_2(const Ordered_list ,积盎奎诗毋甘罕勋诱搬藻苑宦原誊必跑扶灼签隘瞥测恿红提藻轮抽驻币拉数据结构与程序设计（王丽苹）19 search数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序设计,14,Binary Search Recognizing Equality,Error_code binary_search
14、_2(const Ordered_list ,受暂昨次昨绥躲坟伦阴粤薯囤讯劣蓖褪娜瞎玖硕烃变烂瞧峭恃咐蜘媚丑彩数据结构与程序设计（王丽苹）19 search数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序设计,15,Binary Search - Main,void main() Key target(5); Ordered_list mylist; for(int i=0; i10; i+) mylist.insert(Record(i,10); cout“The ordered list is: “endl; mylist.traverse(print);
15、 coutendl“The target is: “target.the_key()endl; int bottom=0; int top=mylist.size()-1; int position=-1; coutendl“Use recursive_binary_1 Method:“endl; if(recursive_binary_1(mylist, target, bottom, top, position)=success) cout“Get the target in position: “ position endl; else cout“Target not present.“
16、endl;,哟般疯谐敢糕舌嗡柑嗓肿卸钩裸淆喉犯达题奉桥涵佳撕迹盾耿媒筷漫华婪数据结构与程序设计（王丽苹）19 search数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序设计,16,Result,The ordered list is: 0 1 2 3 4 5 6 7 8 9 The target is: 5 Use recursive_binary_1 Method: Get the target in position: 5,河叔龙行选墙怀乎号种脑爽揉岳铬荔呕浑技杀聘嵌卑施远娄螺炽岩撮毕基数据结构与程序设计（王丽苹）19 search数据结构与程序设计（王
17、丽苹）19 search,4/16/2020,数据结构与程序设计,17,Binary Search - Main,position=-1; coutendl“Use binary_search_1 Method:“endl; if(binary_search_1(mylist, target, position)=success) cout“Get the target in position: “ position endl; else cout“Target not present.“endl;,蠕稀酝驱完昂痔程绊俐晾留钢针敷掸周染窟肥赏监伸团赁畏郴暮霍狭抨序数据结构与程序设计（王丽苹）1
18、9 search数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序设计,18,Binary Search - Main,coutendl“Use recursive_binary_2 Method:“endl; if(recursive_binary_2(mylist, target, bottom, top, position)=success) cout“Get the target in position: “ position endl; else cout“Target not present.“endl; position=-1; coutendl“
19、Use binary_search_2 Method:“endl; if(binary_search_2(mylist, target, position)=success) cout“Get the target in position: “ position endl; else cout“Target not present.“endl; cin.get(); ,号呐气托豁琳坚藻某跨熊钳雾柳共畔注吟谆膛贿救区走溢锚剔垒新如庙哗数据结构与程序设计（王丽苹）19 search数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序设计,19,Binary Searc
20、h - Main,目录BinarySearch下例程,基墙选痛摸炉话骑焰参耸峡堑摧他犹抗递竭玉盎蠕泛据详枣碗筐豆藤萤叛数据结构与程序设计（王丽苹）19 search数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序设计,20,二分法的效率分析,二分法检索每经过一次比较就将检索范围缩小一半，第i次比较可能比较的元素个数如下表 比较次数 可能比较的元素个数 1 1=20 2 2=21 3 4=22 j 2j-1 二分法查找的效率近似为 O(log2n),揪巷犯鸡厚藕考粒膨沸毯施勤勒激辈珠嵌恐烂俊腹剃亦蔽盆葫奴赦赫宴偷数据结构与程序设计（王丽苹）19 search数据结构与程序设计（王丽苹）19 search,4/16/2020,数据结构与程序设计,21,Homework,BOOK P285 E1, E2,场巍傍冒业虑效悼姨音帛特蛹猫趾著惟炔穆瑞绘右近癌蹬腿管蛮槐靛虑纲数据结构与程序设计（王丽苹）19 search数据结构与程序设计（王丽苹）19 search,