点击添加文本 点击添加文本 点击添加文本 点击添加文本 热身游戏--猜！猜！猜！ 5 2 4 8 7 3 对 分 查 找 及 其 程 序 实 现 点击添加文本 点击添加文本 点击添加文本 点击添加文本 目录 对分查找的思想 对分查找的实例 对分查找的过程 对分查找的效率 返回 点击添加文本 点击添加文本 点击添加文本 点击添加文本 对分查找的思想 (1).被查找的数组是有序的。 (2).首先将要查找的数与有序数组中间位置的数比较，如果中间位置上的数与查找的数不同，则可确定应该在数组的前半部分还是后半部分继续查找。 (3).在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。 返回 点击添加文本 点击添加文本 点击添加文本 点击添加文本 对分查找的过程 如果，要查找的值在数组的前半部分。例如：查找22 假设有一组数组a（7）， 用于存放升序元素值。用i表示查找范围的起始位置的下标，j表示终止位置的下标,mid表示中间位置元素的下标。 11 22 33 44 55 66 77 第一次查找范围为整组，即a(1)-a(7)，mid=(1+7)\2=4,a(mid)>key，即44>22,比较后j=mid-1 第一次 i j mid 第二次 i j mid 11 22 33 44 55 66 77 11 22 33 44 55 66 77 第二次查找范围为前半组，即a(1)-a(3) ，mid=(1+3)\2=2,a(mid)=key,找到了！ 点击添加文本 点击添加文本 点击添加文本 点击添加文本 对分查找的过程 如果，要查找的值为后半部分呢？例如：查找77 11 22 33 44 55 66 77 第一次 i j mid 第二次 i j mid 11 22 33 44 55 66 77 第三次 i j mid 11 22 33 44 55 66 77 第二次查找范围为后半组，即a(5)-a(7) ，mid=(5+7)\2=6,a(mid)
key，即66>50,比较后j=mid-1 ,即j=5 第一次查找范围为整组，即a(1)-a(7)，mid=(1+7)\2=4,a(mid)key，55>50,比较后j=mid-1,即j=4 点击添加文本 点击添加文本 点击添加文本 点击添加文本 对分查找的过程 归纳： 当数组内元素值为升序排列时 (1)如果keya(mid),新查找的范围为后半部分,j值不变,i=mid+1 (3) ①如果找到了,查找会结束； ②查找范围大于等于一个元素时,即在i<=j时重复查找,如果查 找完最后一个元素，即i>j还是找不到,查找也会结束 返回 点击添加文本 点击添加文本 点击添加文本 点击添加文本 对分查找的流程图 开 始 结 束 i?1,j?n j?m-1 计算中点m?(i+j)\2 i?m+1 a(m)=key i<=j Key
