Question

C++折半查找的基本思想和步骤

Answer 1

折半查找的基本思想是：对于有序表，查找时先取表中间位置的记录关键字和所给关键字进行比较，若相等，则查找成功；如果给定值比该记录关键字大，则在后半部分继续进行折半查找；否则在前半部分进行折半查找，直到查找范围为空而查不到为止。
折半查找的过程实际上死先确定待查找元素所在的区域，然后逐步缩小区域，直到查找成功或失败为止。
算法中需要用到三个变量，low表示区域下界，high表示上界，中间位置mid=(low+high)/2
算法：
#define
MAXLEN
n
......
......
int
binsearch（DATATYPE
A[],int
k)
{
int
low,high;
low=0;
high=MAXLEN-1;
while(low<=high)
{
mid=low+high)/2;
if(k==A[mid].key)
return
mid;
//查找成功，返回被查元素在表中的相对位置
else
if(k>A[mid].key)
low=mid+1;
else
high=mid-1;
}
return
-1;
//查找失败，返回-1
}
这只是算法，运用要靠你自己！