我想看看高手写的二分查找法。。。
例：
有15个整数按由大到小顺序存放在一个数组中，输入一个整数，要求用二分查找法找出该数是数组中第几个元素的值。如果该数不在数组中，则打印“找不到”
下午我把我写的帖出来 学习一下。。。
[解决办法]
template <class T>
int binSearch(T &array,int begin,int end,unsigned int target)
{
int mid = (end-begin)/2 + begin;
if(end > begin)
{
if(array[mid] == target)
return mid;
else if(array[mid] < target)
return binSearch(array,mid+1,end,target);
else
return binSearch(array,begin,mid,target);
}
else
{
if(array[begin] == target)
return begin;
else
return -1;
}
}
//返回> = target的最小数的下标
template <class T>
int findAbove(T &array,int begin,int end,unsigned int target)
{
int mid = (end-begin)/2 + begin;
if(end - begin > = 2)
{
if(array[mid] > = target && array[mid-1] < target)
return mid;
else if(array[mid] < target)
return findAbove(array,mid+1,end,target);
else
return findAbove(array,begin,mid,target);
}
else
{
if(array[begin] > = target)
return begin;
else if(array[end] > = target)
return end;
else
return -1;
}
}
//返回 <target的最大数的下标
template <class T>
int findBelow(T &array,int begin,int end,unsigned int target)
{
int mid = (end-begin)/2 + begin;
if(end - begin > = 2)
{
if(array[mid] < target && array[mid+1] > = target)
return mid;
else if(array[mid] < target)
return findBelow(array,mid+1,end,target);
else
return findBelow(array,begin,mid,target);
}
else
{
if(array[end] < target)
return end;
else if(array[begin] < target)
return begin;
else
return -1;
}
}
[解决办法]
lz的帖子很好，说明了一个简单的算法也很难给出正确的实现：）
todototry(来csdn，学会扯淡了...)
递归版本在未找到元素的情况下不会正常中止
netxuning(大字报写手)
int hi = num; //这里hi应该初始化为num-1，而不是num
seki1018()
实现上没有问题，不过一般的算法应该实现为一个过程，而不是和输入输出混在一起，这样既不可以重用，改起来也不太方便
sniperhuangwei()
很好的实现，不过array应该是T *，target应该是T ，或者const T &
