二分查找的递归和非递归实现
如果面试题要求在已排序的数组(或者部分排序的数组)中查找一个数字或者统计某个数字出现的次数,我们都可以考虑尝试二分查找算法。
二分查找的递归实现代码:
int BinarySearch(int num,int array[],int low,int high)
{
if(low > high) return -1;
int mid = low + (high-low)/2;
if(array[mid]>num) return BinarySearch(num,array,low,mid-1);
else if(array[mid]<num) return BinarySearch(num,array,mid+1,high);
else return mid;
}
二分查找的迭代实现代码:
int BinarySearch(int num,int array[],int len)
{
int low = 0;
int high = len-1;
while(low <= high){
int mid = low + (high - low)/2;
if(array[mid] > num) high = mid - 1;
else if(array[mid] < num) low = mid + 1;
else return mid;
}
return -1;
}
一条评论
添加新评论
- Pingback: C++技术岗位-笔试面试题总结【持续更新…】 - Veaxen's