二分查找算法例题

2024-07-02 04:18| 来源: 网络整理| 查看: 265

目录一、问题描述二、实现思路三、解题代码四、运行结果

一、问题描述

对于给定11个数据元素的有序表：(2，3，10，15，20，25，28，29，30，35，40)，若查找给定值为20的元素，将依次与表中哪些元素比较？若查找给定值为26的元素，将依次与哪些元素比较？假设查找表中每个元素的概率相同，求查找成功时的平均查找长度和查找不成功时的平均查找长度。

二、实现思路

对于给定11个数据元素的有序表：(2，3，10，15，20，25，28，29，30，35，40)，采用二分查找，若查找给定值为20的元素，共比较4次。若查找给定值为26的元素，依次与25,30,28元素比较，共比较3次。假设查找表中每个元素的概率相同，根据查找判定树图1可得，在查找成功时会找到某个内部结点，则成功时的ASL成功=（11+22+43+44）/11=3，在查找不成功时,会找到图中某个外部结点,则不成功时的平均查找长度为ASL不成功=（43+84）/12=3.67。折半查找的基本思路是设R[low…high]是当前的查找区间,首先确定该区间的中点位置mid=[(low+high)/2]，然后将待查的k值与R[mid].key比较: (1)若k=R[mid].key,则查找成功并返回该元素的逻辑序号。 (2)若k R[mid].key.则关键字为k的元素必在mid的右子表R[mid+1…high]中。即新的查找区间是右子表R[mid+1…high]，下一次查找是针对新的查找区间进行的。图1 查找判定树

三、解题代码 #include #include using namespace std; #define MAX 50 typedef int KeyType; //定义关键字类型 typedef int InfoType; typedef struct { KeyType key; //关键字项 InfoType data; //其他数据类型 }RecType; //查找元素的类型 //折半查找算法,返回查找元素位置并纪录比较路径 int BinSearch(RecType R[], int n, KeyType k,int cmp[]) { int count = 0; //比较路径数组的下标 int low = 0, high = n - 1, mid; while (low cmp[count++] = R[mid].key; //纪录比较路径 cmp[count] = -1; //作为路径结尾的标志 return mid + 1; } if (R[mid].key > k) //继续在R[low..mid-1]中查找 { cmp[count++] = R[mid].key; high = mid - 1; } else { cmp[count++] = R[mid].key; low = mid + 1; //继续在R[mid+1..high]中查找 } } return 0; } int main() { int n,key,i; RecType R[MAX]; //比较路径 int cmp[MAX] = { 0 }; cout n; cout cout

【本文地址】

公司简介

联系我们