折半查找法
：在有序表中，把待查找数据值与查找范围的中间元素值进行比较，会有三种情况出现：
1） 待查找数据值与中间元素值正好相等，则放回中间元素值的索引。
2） 待查找数据值比中间元素值小，则以整个查找范围的前半部分作为新的查找范围，执行1），直到找到相等的值。
3） 待查找数据值比中间元素值大，则以整个查找范围的后半部分作为新的查找范围，执行1），直到找到相等的值
按照二叉树来理解：中间值为二叉树的根，前半部分为左子树，后半部分为右子树。折半查找法的查找次数正好为该值所在的层数。等概率情况下，约为
log2(n+1)-1
代码如下:
last)
{
return -1;
}
while(beg <= last)
{
mid = (beg + last) / 2;
if (x == data[mid] )
{
return mid;
}
else if (data[mid] < x)
{
beg = mid + 1;
}
else if (data[mid] > x)
{
last = mid - 1;
}
}
return -1;
}
//递归法
int IterBiSearch(int data[],int last)
{
int mid = -1;
mid = (beg + last) / 2;
if (x == data[mid])
{
return mid;
}
else if (x < data[mid])
{
return IterBiSearch(data,x,beg,mid - 1);
}
else if (x > data[mid])
{
return IterBiSearch(data,mid + 1,last);
}
return -1;
}
//主函数
int _tmain(int argc,_TCHAR* argv[])
{
int data1[60] = {0};
int no2search = 45;
cout << "The array is : " << endl;
int siz = sizeof(data1)/sizeof(int);
for (int i = 0; i < siz; i++)
{
data1[i] = i;
cout << data1[i] << " ";
}
cout << endl;
int index = -1;
//index = BiSearch(data1,no2search,siz);
index = IterBiSearch(data1,siz);
cout << "Index of " << no2search << " is " << index << endl;
getchar();
return 0;
}
代码如下:
array[midPoint-1]){
lowPoint=midPoint+1;
}
else if(x
