首页 > 代码库 > 算法学习笔记（一）：二分法及其实现
算法学习笔记（一）：二分法及其实现
基本思想：二分法的一个前提是序列已经是有序的，然后将待查找值与序列的中点比较。根据比较结果，选择下一步比较的部分。二分查找（binary search）就是一个不断重复这一查找过程，直到找到这个值。
算法复杂度：O（lgn）
算法实现：
一：迭代法
int bin_search_iteration(int arr[],int start,int end,int x){ while (start<end) { int mid = (start + end) / 2; if (arr[mid]<x) { start = mid + 1; } else if (arr[mid]==x) { return mid; } else { end = mid - 1; } } if (start == end) return arr[start] == x ? start : -1; else { return -1; }}
二：递归法
int bin_search(int arr[],int start,int end,int x){ if (start == end) return arr[start]==x?start:-1; int mid = (start+end) / 2; if(arr[mid]==x) { return mid; } else if(arr[mid]>x) { return bin_search(arr, start,mid, x); } else { return bin_search(arr, mid+1,end, x); } }
算法学习笔记（一）：二分法及其实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。