1顺序表 在顺序表上查找的基本思想是:从顺序表的一端开始,用 给定数据元素的关键字逐个和顺序表中各数据元素的关键字 匕较,若在顺序表中查找到要查找的数据元素,则查找成功 函数返回该数据元素在顺序表中的位置;否则查找失败,函 数返回-1
1.顺序表 在顺序表上查找的基本思想是：从顺序表的一端开始，用 给定数据元素的关键字逐个和顺序表中各数据元素的关键字 比较，若在顺序表中查找到要查找的数据元素，则查找成功， 函数返回该数据元素在顺序表中的位置；否则查找失败，函 数返回-1
查找函数设计如下 int Seqsearch(Data Type all, int n, Key Type key) inti=0 while(i< n & ai key !=key)i++ if(ai]. key=- key) return i; else return -l 查找成功时的平均查找长度ASL为: ASL=∑PC1=∑=(n+1)/2
查找函数设计如下： int SeqSearch(DataType a[], int n, KeyType key) { int i = 0; while(i < n && a[i].key != key) i++; if(a[i].key == key) return i; else return -1; } 查找成功时的平均查找长度ASL为： = = = = = + n i i n i i i n n ASL PC 1 1 ( 1)/ 2 1
2有序顺序表 有序顺序表上的查找算法主要有顺序查找和折半查找两种方法。 、顺序查找 有序顺序表上的顺序查找算法和顺序表上的查找算法方法类同 二、二分查找(又称折半查找) 算法的基本思想:先给数据排序(例如按升序排好),形成 有序表,然后再将key与正中元素值相比,着key小,则缩小 至前半部內查找;再取其中值比较,每次缩小1/2的范围,直 到查找成功或失败为止。反之,如果key大,则缩小至后半部 内查找
2.有序顺序表 有序顺序表上的查找算法主要有顺序查找和折半查找两种方法。 一、顺序查找 有序顺序表上的顺序查找算法和顺序表上的查找算法方法类同 二、二分查找（又称折半查找） 算法的基本思想：先给数据排序（例如按升序排好），形成 有序表，然后再将key与正中元素值相比，若key小，则缩小 至前半部内查找；再取其中值比较，每次缩小1/2的范围，直 到查找成功或失败为止。反之，如果key大，则缩小至后半部 内查找
二分查找算法如下 int BiSearch dataType all, int n, Key Type key) int low=0,high=n-1;/确定初始查找区间上下界 int mid; while(low < high) mid=(ow+high)/2;/确定查找区间中心下标 if( amid]. key=key) return mid;/查找成功 else if(a]. key key) low=mid+1 else high= mid-1 return-1; /查找失败
二分查找算法如下： int BiSearch(DataType a[], int n, KeyType key) { int low = 0, high = n - 1; //确定初始查找区间上下界 int mid; while(low <= high) { mid = (low + high)/2;//确定查找区间中心下标 if(a[mid].key == key) return mid; //查找成功 else if(a[mid].key < key) low = mid + 1; else high = mid - 1; } return -1; //查找失败 }
算法分析 平均查找长度ASL为: ASL=∑PC=∑2 n+ log2(n+1)-1≈log2n
算法分析 平均查找长度ASL为： n n n n i n ASL PC n i k i i i i 2 2 1 1 1 log ( 1) 1 log 1 2 1 + − + = = = = = −