您现在的位置是:首页 > 文章详情

【算法导论】二分查找

日期:2018-08-29点击:322

1. 描述(查找算法):

输入:n个数的一个序列 A = (a1, a2, a3,.....an)和一个值v

输出:下表 i 使得 v=A[i] 或者 v 不在A中出现时,输出 NIL

二分查找的前提是A必须是有序序列, 以下全部假设是A是非降序序列

2. 图解

3. 伪代码

//用递归 BINARY_SEARCH(A, v, low, high) if(low <= high) mid = (low+high)/2 //向下取整 if v == A[mid] return mid; else if v < A[mid] return BINARY_SEARCH(A, v, low, mid-1) else if v > A[mid] return BINARY_SEARCH(A, v, mid+1, high) return NIL //用循环 BINARY_SEARCH(A, v) low = 1 high = A.length while low <= high mid = (low + high)/2 //向下取整 if v == A[mid] return mid else if v < A[mid] high = mid -1 else if v > A[mid] low = mid +1
return NIL

4. 代码实现

java

//用循环 int binarySearch1(int[] A, int v){ int low = 0; int high = A.length; while (low <= high) { int mid = (low + high)/2; if (v == A[mid]) return mid; else if (v < A[mid]) high = mid - 1; else if (v > A[mid]) low = mid + 1; return -1; } //用递归 int binarySearch2(int[] A, int v, int low, int high) { if (low <= high) { int mid = (low + high)/2; if (v == A[mid]) return mid; else if (v < A[mid]) return binarySearch2(A, v, low, mid - 1); else if (v > A[mid]) return binarySearch2(A, v, mid + 1, high); return -1; }

python

# 用循环 def binary_search1(nums, v): low = 0 high = len(nums) while low <= high: mid = int((low + high) / 2) if v == nums[mid]: return mid else: if v <= nums[mid]: high = mid - 1 else: if v > nums[mid]: low = mid + 1 return -1 # 用递归 def binary_search2(nums, v, low, high): if low <= high: mid = int((low + high) / 2) if v == nums[mid]: return mid else: if v < nums[mid]: return binary_search2(nums, v, low, mid - 1) else: if v > nums[mid]: return binary_search2(nums, v, mid + 1, high) return -1

 

C语言

//用循环  int binary_search1(int arr[], int v, int len) { int low, mid, high; low = 0, high = len-1; while (low <= high) { mid = (low + high) / 2; if (v == arr[mid]) return v; else if (v > arr[mid]) low = mid + 1; else if (v < arr[mid]) high = mid -1; } return -1; } //用递归  int binary_search2(int arr[], int v, int low, int high) { int mid; if (low <= high) { mid = (low + high) / 2; if (v == arr[mid]) return v; else if (v > arr[mid]) return binary_search2(arr, v, mid + 1, high); else if (v < arr[mid]) return binary_search2(arr, v, low, mid - 1); } return -1; }

 

 

 

原文链接:https://yq.aliyun.com/articles/653970
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章