没有革命的理论就没有革命的运动1、折半查⼜称为⼆分查，是⼀种效率较⾼的查⽅法。
2、折半查的前提条件：
查过程中，先确定待查记录在表中的范围，然后逐步缩⼩范围(每次将待查记录所在区间缩⼩⼀半)，直到到或不到记录为⽌。
3、查的算法可以简述为以下：
⽤Low、High和Mid表⽰待查区间的下界、上界和中间位置指针，初值为Low=1，High=n。
⑴ 取中间位置Mid：Mid=(Low+High)/2；
⑵ ⽐较中间位置记录的关键字与给定的K值：
① 相等： 查成功；
② ⼤于：待查记录在区间的前半段，修改上界指针：High=Mid-1，转⑴ ；
③ ⼩于：待查记录在区间的后半段，修改下界指针：Low=Mid+1，转⑴ ；
直到越界(Low>High)，查失败。
4、查的算法分析
① 查时每经过⼀次⽐较，查范围就缩⼩⼀半，该过程可⽤⼀棵⼆叉树表⽰：
◆ 根结点就是第⼀次进⾏⽐较的中间位置的记录；
◆ 排在中间位置前⾯的作为左⼦树的结点；
◆ 排在中间位置后⾯的作为右⼦树的结点；
峰尾对各⼦树来说都是相同的。这样所得到的⼆叉树称为判定树(Decision Tree)。
② 将⼆叉判定树的第 ㏒2n +1层上的结点补齐就成为⼀棵满⼆叉树，深度不变，h= ㏒2。
③ 由满⼆叉树性质知，第i 层上的结点数为2i-1(i≤h) ，设表中每个记录的查概率相等，即Pi=1/n，查成功时的平均查
长度ASL：
当n很⼤ (n>50)时， ASL≈ ㏒2(n+1)-1
5、折半查的代码实现
#include<iostream>
using namespace std;
//递归折半
bool fold_findo(int m,int arr[],int low,int high)
{
bool result =false;
if(low <= high)
{
int mid =(low + high)/2;
if(m == arr[mid])
{
return true;
}else if(m < arr[mid])
{
result =fold_findo(m, arr, low, mid -1);
}else
{
result =fold_findo(m, arr, mid +1, high);
}
return result;
}else
{
return false;
}
}
//迭代折半
bool fold_finds(int m,int arr[],int low,int high)
{
int mid;
while(low <= high)
{
mid =(low + high)/2;
if(m == arr[mid])
{
return true;
}else if(m < arr[mid])
{
high = mid -1;
}else
{
low = mid +1;
}真菌恐惧症
}
return false;
}
北京青春int main()
{
int m;//需要查的元素
int arr[]={-10,-5,0,1,2,4,6,9,12,18,20,26}; int len =sizeof(arr)/sizeof(int);
cin >> m;
特朗普不适合当总统bool result =fold_finds(m, arr,0, len -1);
if(result ==true)
{
cout <<"Find yes!"<< endl;
}else
{
cout <<"No find!"<< endl;
}
智慧启迪return0;
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议