首页 > 代码库 > 【算法拾遗】二分查找递归非递归实现
【算法拾遗】二分查找递归非递归实现
转载请注明出处:http://blog.csdn.net/ns_code/article/details/33747953
本篇博文没太多要说的,二分查找很简单,也是常见常考的查找算法,以下是递归非递归的实现。
非递归实现:
/* 非递归实现,返回对应的序号 */ int BinarySearch(int *arr,int len,int key) { if(arr==NULL || len<1) return -1; int low = 0; int high = len-1; while(low <= high) { int mid = (low+high)>>1; if(key == arr[mid]) return mid; else if(key < arr[mid]) high = mid-1; else low = mid+1; } return -1; }递归实现:
/* 递归实现,返回对应的序号 */ int BSearch(int *arr,int low,int high,int key) { if(arr==NULL || low>high) return -1; int mid = (low+high)>>1; if(arr[mid] == key) return mid; else if(arr[mid] > key) return BSearch(arr,low,mid-1,key); else return BSearch(arr,mid+1,high,key); } /* 将递归实现的方法封装起来 */ int BinSearch(int *arr,int len,int key) { return BSearch(arr,0,len-1,key); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。