NO.5计算机软件基础 新查找课件.ppt

第 1 章　 数据结构 ;;基本思路： 从表中第一个元素开始，将给定的值与表中逐个元素的关键字比较。直到两者相等表示找到，查找成功。否则就是表中无要找的元素，查找失败。 ; ; ; ; ; ;基本思路： 从表中第一个元素开始，将给定的值与表中逐个元素的关键字比较。直到两者相等表示找到，查找成功。否则就是表中无要找的元素，查找失败。 ;基本思路： 从表中第一个元素开始，将给定的值与表中逐个元素的关键字比较。直到两者相等表示找到，查找成功。否则就是表中无要找的元素，查找失败。 ; 思想：先确定待查找记录所在的范围，然后逐步缩小范围， 直到找到或确认找不到记录为止。 适用条件：必须在具有顺序存储结构的有序表(表中元素按关键值升序或降序存放)中进行。 ; 例在含有9个数的升序线性表中查找68的过程如下图 ; 例在含有16个数的升序线性表中查找39和17的过程如下图 ; 2 4 5 8 16 20 29 36 37 39 41 42 45 50 52 58 ;二分查找(折半查找) 查找效率高 前提: 查找表中的数据元素必须有序。 算法:1) 确定区间的中间位置 mid =(left + right)/2 2) 用给定值与中间位置的关键字值比较；若相等，则查找成功； 若给定值大,新查找区为后半区； 若给定值小,新查找区为前半区。 3)对缩小的区域重复上述步骤； ;二分法查找程序;查找总结