© 排序与查找 顺序查找 二分查找 团 选择排序法 气泡排序法 司 LoCCS
排序与查找 顺序查找 二分查找 选择排序法 气泡排序法
二分查找 数组元素已按某一顺序排序，如数字的大小顺序、字母的字 母序等。以下讨论中都假设是按升序排序。 过程： 设定查找范围的上下界：Ih,rh ·找出中间元素的位置：mid=（h+rh)/2 比较中间元素与欲查找的元素key。如key等于中间元 素，则mid就是要查找的元素的位置；如key>中间元 素，则从Ih一mid的这些元素不可能是要查找的元素， 修正查找范围为Ih=mid+1到rh;如key〈中间元素， 则从mid-rh的这些元素不可能是要查找的元素，修正查 找范围为Ih到rh=mid-1;如h>rh,则要查找 的元素不存在，否则返回第二步。 如在数组CityTable中查找元素San Francisco的过程 下所示。 LoCcS
二分查找 数组元素已按某一顺序排序，如数字的大小顺序、字母的字 母序等。以下讨论中都假设是按升序排序。 过程： • 设定查找范围的上下界：lh, rh • 找出中间元素的位置：mid = ( lh + rh ) / 2 • 比较中间元素与欲查找的元素 key。如 key 等于中间元 素，则 mid 就是要查找的元素的位置；如 key > 中间元 素，则从 lh – mid 的这些元素不可能是要查找的元素， 修正查找范围为 lh = mid + 1到 rh；如key < 中间元素， 则从mid - rh的这些元素不可能是要查找的元素，修正查 找范围为 lh 到 rh = mid - 1；如 lh > rh，则要查找 的元素不存在，否则返回第二步。 如在数组 CityTable 中查找元素 San Francisco 的过程如 下所示
⑧ 二分查找过程 0 Atlanta 0 Atlanta 0 Atlanta 1 Boston 1 B6sto— 1 Boston 2 Chicago 2 Chicago- 2 Chicago- 3 Denver 3 Denver 3 Denver 4 Detroit 4 Detroit— 4 Detroit 5 Houston 5 osto班 5 osto在 6 Los Angeles 6 Los Angeles 6 Los Angeles 7 Miami 7 Miami Miami 8 New York 8 New York 8 时ewor味 9 Philadelphia 9 Philadelphia 9 Philadelphia 10 San 10 San Francisco 10 San Francisco Francisco 11 Seattle 11 Seattle 11 Seattle 6配c$
二分查找过程 0 Atlanta 1 Boston 2 Chicago 3 Denver 4 Detroit 5 Houston 6 Los Angeles 7 Miami 8 New York 9 Philadelphia 10 San Francisco 11 Seattle 11 Seattle 10 San Francisco 9 Philadelphia 8 New York 7 Miami 6 Los Angeles 5 Houston 4 Detroit 3 Denver 2 Chicago 1 Boston 0 Atlanta 11 Seattle 10 San Francisco 9 Philadelphia 8 New York 7 Miami 6 Los Angeles 5 Houston 4 Detroit 3 Denver 2 Chicago 1 Boston 0 Atlanta