(3)算法描述 算法步骤: stepl首先确定整个查找区间的中间位置, mid =int(( left right )/2) step2用待查关键字值与中间位置的关键字值进行 比较; 若相等,则查找成功; 若大于,则在后半区域继续进行二分查找; 若小于,则在前半区域继续进行二分查找。 Step3对确定的缩小区域再按二分公式,重复上述 上页步骤; 停止放映 最后,得到结果: 要么,查找成功,要么,查找失败。 存储结构 用一维数组存放。 第16页
下一页 上一页 停止放映 第 16 页 (3)算法描述 ⚫ 算法步骤： –step1 首先确定整个查找区间的中间位置， mid = int(（ left + right ）/ 2) –step2 用待查关键字值与中间位置的关键字值进行 比较； • 若相等，则查找成功； • 若大于，则在后半区域继续进行二分查找； • 若小于，则在前半区域继续进行二分查找。 –Step3 对确定的缩小区域再按二分公式，重复上述 步骤； –最后，得到结果： • 要么，查找成功， 要么，查找失败。 ⚫ 存储结构 –用一维数组存放
折半查找算法举例 ●对给定数列(有序){3,5,11,17,21,23,28, 30,32,50},共10个数,按折半查找算法,查找关 键字值为30的数据元素。找30 第1次:{3,5,11,17,21,23,28,30,32,50} left mid right mid1=(1+10)/2=5 上一页 第2次:{23,28,30,32,50 left mid right 停止放映 mid2=(6+10)2=8 下一页 第17页
下一页 上一页 停止放映 第 17 页 折半查找算法举例 ⚫ 对给定数列（有序）{ 3，5，11，17，21，23，28， 30，32，50}，共10个数，按折半查找算法，查找关 键字值为30的数据元素。找30： 第1次： { 3，5，11，17，21，23，28，30，32，50 } mid1= （1+10）/2 = 5 第2次： { 23，28，30，32，50 } mid2 = （6+10） /2 = 8 left mid right left mid right
在有序数4、8、9、10、11、13、19中查找9 初始:low=1,hgh=7 mid=int(1+7)/2]=4 比较key=9<A[4]=10向左 High mid-1=3 md=4但key=9<10,向左 上一页 key 停止放映 8910111319 下一页 7 lowe high=7
下一页 上一页 停止放映 折半查找演示（1） 0 1 2 mid=4 但 key=9 < 10, 向左 key 4 8 9 10 11 13 19 3 4 5 6 7 high=7 low=1 在有序数4、8、9、10、11、13、19中查找 9 初始：low=1, high=7 mid=int[(1+7)/2]=4 比较 key=9 < A[4]=10 向左 High=mid-1=3
在有序数4、8、9、10、11、13、19中查找9 初始:low=1,hgh=3 mid=4 上一页 key 停止放映 8910111319 下一页 7 lowe high=3(mid-1)
下一页 上一页 停止放映 折半查找演示（1） 0 1 2 mid=4 key 4 8 9 10 11 13 19 3 4 5 6 7 low=1 high=3（mid-1） 在有序数4、8、9、10、11、13、19中查找 9 初始：low=1, high=3
在有序数4、8、9、10、11、13、19中查找9 初始:low=1,high=3 mid=int(1+3)/2]=2 上一页 mid=2 key 停止放映 8910111319 下一页 7 lowe high=3(mid-1)
下一页 上一页 停止放映 折半查找演示（1） 0 1 2 mid=2 key 4 8 9 10 11 13 19 3 4 5 6 7 low=1 high=3（mid-1） 在有序数4、8、9、10、11、13、19中查找 9 初始：low=1, high=3 mid=int[(1+3)/2]=2