成都网站公司建设,做暧暧视频网站,查询网站服务器,wordpress 功能 wordpress.org二分查找
什么是二分查找#xff1f;
二分查找是一种针对有序集合#xff0c;每次将要查找的区间缩小一半#xff0c;直到找到查找元素#xff0c;或区间被缩小为0。
如何实现二分查找#xff1f;
实现有3个注意点#xff1a;
终止条件是 low high 2.求中点的算…二分查找
什么是二分查找
二分查找是一种针对有序集合每次将要查找的区间缩小一半直到找到查找元素或区间被缩小为0。
如何实现二分查找
实现有3个注意点
终止条件是 low high 2.求中点的算法是 low (high - low)/2 3.low和high的更新是lowmid1 即到更大的区间找 highmid-1 即到更小的区间找。
非递归实现 // 终止条件lowhigh 当lowhigh时midlow(high-low)/2lowhigh,即没有等号将少比较一个点// 中点 mid low (high-low)/2 即以low为起点计算low和high之间的中点// midvalue 找大区间 lowmid1midvalue找小区间highmid-1public int binSearch(int[] arr,int n,int value){int low0;int highn-1;while(lowhigh){int midlow((high-low)1);//int midlow(high-low)/2;if(arr[mid]value){lowmid1;} else if(arr[mid]value){highmid-1;} else{return mid;}}return -1;}递归实现
// 二分查找的递归实现
public int bsearch(int[] a, int n, int val) {return bsearchInternally(a, 0, n - 1, val);
}private int bsearchInternally(int[] a, int low, int high, int value) {if (low high) return -1;int mid low ((high - low) 1);if (a[mid] value) {return mid;} else if (a[mid] value) {return bsearchInternally(a, mid1, high, value);} else {return bsearchInternally(a, low, mid-1, value);}
}二分查找有哪些局限性
1. 二分查找依赖的是顺序表结构也就是数组 2. 二分查找要求数据有序 3. 数据量太小不适合二分查找除非每个数据的操作非常耗时比如数组中存储的都是长度超过 300 的字符串如此长的两个字符串之间比对大小就会非常耗时。 4. 数据量太大也不适合二分查找因为数组需要占用大量连续的空间 5. 动态数据不适合二分查找频繁的插入和删除在数组结构下效率很低
思考题
如何编程实现“求一个数的平方根”要求精确到小数点后 6 位。 可以用牛顿弦切法来求平方跟 double number 2; //待求平方根的数 double xini 10;//初始点 while(xinixini - number 1e-6) { xini (number xinixini)/2/xini; } // xini为平方根我刚才说了如果数据使用链表存储二分查找的时间复杂就会变得很高那查找的时间复杂度究竟是多少呢 链表不像数组那样支持随机访问所以链表主要花的是查找第n个节点的访问的时间。 第一次需要遍历n/2个节点 第二次需要遍历n/4个节点 第三次需要遍历n/8个节点
n/2 n/4 n/8 … 和约等于n因此算法复杂度为O(n)单考虑到其他二分查找的额外操作会比直接遍历循环查找慢一些。
二分查找有哪些变体问题
对于有序数组中有重复元素而言二分查找通常有以下4个变体问题。 查找第一个值等于给定值的元素 查找最后一个值等于给定值的元素 查找第一个大于等于给定值的元素 查找最后一个小于等于给定值的元素
这些都是查找等于给定值的变体问题想一想你有什么思路可以实现呢
如何实现变体的二分查找
arr[mid]和value的值的比较有三种情况大于小于等于 那对于问题1和2而言我们要特殊处理的等于的情况 问题3要特殊处理大于等于的情况 问题4要特殊处理小于等于的情况。 问题1的特殊处理逻辑 等于的情况下我们mid的下标有可能是0即数组的第一个元素那么我们直接返回mid就好了 那其余情况就是mid0那么我们就看mid的前一个元素是否等于value如果不等于说明mid是第一个等于value的元素也直接返回 如果等于mid那么我们就需要在前面的区间去查找了即 high mid - 1;
那问题2,3,4和1的处理思路类似可以试着自己实现。
1 public int binSearchFirst(int[] arr,int n,int value){int low0;int highn-1;while (lowhigh) {int mid low (high - low) / 2;if(arr[mid]value){lowmid1;} else if(arr[mid]value){highmid-1;} else{// 需要特殊处理的是等于的情况// 1.看mid是否为第一个元素是返回mid// 2.看mid的前一个元素是否等于value不等于返回mid// 3.mid的前一个元素等于value那么就应该去前面区间找即 high mid - 1;if(mid0||arr[mid-1]!value) {return mid;}highmid-1;}}return -1;}2 public int binSearchFirst(int[] arr,int n,int value){int low0;int highn-1;while (lowhigh) {int mid low (high - low) / 2;if(arr[mid]value){lowmid1;} else if(arr[mid]value){highmid-1;} else{// 需要特殊处理的是等于的情况// 1.看是mid否为最后一个元素是返回mid// 2.看mid的后一个元素是否等于value不等于返回mid// 3.mid的后一个元素等于value那么就应该去后面区间找即 low mid 1;if(midn-1||arr[mid1]!value) {return mid;}lowmid1;}}return -1;}3 public int binSearchFirst(int[] arr,int n,int value) {int low 0;int high n - 1;while (low high) {int mid low (high - low) / 2;if (arr[mid] value) {// 主要处理大于等于的情况// 1.看mid是否为第一个元素是返回mid// 2.看mid的前一个元素是否小于value是返回mid// 3.前一个元素大于等于value应该去前面区间找即highmid-1if(mid0||arr[mid-1]value){return mid;}high mid - 1;} else {low mid 1;}}return -1;}4 public int binSearchFirst(int[] arr,int n,int value) {int low 0;int high n - 1;while (low high) {int mid low (high - low) / 2;if (arr[mid] value) {// 主要处理大于等于的情况// 1.看mid是否为最后一个元素是返回mid// 2.看mid的后一个元素是否大于value是返回mid// 3.后一个元素小于等于value应该去后面区间找即lowmid1if(midn-1||arr[mid1]value){return mid;}low mid 1;} else {high mid - 1;}}return -1;}二分查找的实际应用场景
绝大部分情况能用二分查找解决的问题我们更倾向使用散列表或二叉查找树 那二分查找其实更适用于近似的查找范围查找问题因为这类问题用上述数据结构都不容易实现。
思考题
我们今天讲的都是非常规的二分查找问题今天的思考题也是一个非常规的二分查找问题。如果有序数组是一个循环有序数组比如 456123。针对这种情况如何实现一个求“值等于给定值”的二分查找算法呢
我们发现循环数组存在一个性质以数组中间点为分区会将数组分成一个有序数组和一个循环有序数组。 如果首元素小于 mid说明前半部分是有序的后半部分是循环有序数组 如果首元素大于 mid说明后半部分是有序的前半部分是循环有序的数组 如果目标元素在有序数组范围中使用二分查找 如果目标元素在循环有序数组中设定数组边界后使用以上方法继续查找。 时间复杂度为 O(logN)。
