9.1.2有序的顺序表的查找与折半查找法 1.有序表 r[1].key≤r[2].key≤..≤r[n].key 2.折半查找( binary search,对半查找,二分查找) 假定k=10 1012182025304010w=1,hig=8 12345678 mid=(lowthig)/2=4 hi 51012 1820253040 low=l, hig=3 mid=(low+hig)/ 2=2 12345678 low mid hig9.1.2 有序的顺序表的查找与折半查找法 1.有序表 r[1].key≤r[2].key≤...≤r[n].key 2.折半查找(binary search,对半查找，二分查找) 假定 k=10 5 10 12 18 20 25 30 40 1 2 3 4 5 6 7 8 ↑ ↑ ↑ low mid hig low=1,hig=8 mid=(low+hig)/2=4 5 10 12 18 20 25 30 40 1 2 3 4 5 6 7 8 ↑ ↑ ↑ low mid hig low=1,hig=3 mid=(low+hig)/2=2