天津工程建设信息网站,医疗电子的网站建设,中国菲律宾友谊,建筑劳务公司名字起名大全有单调性的数列一定可以使用二分#xff0c;没有单调性的题目也可能可以使用二分#xff1b; #xff08;一#xff09;整数二分
二分的本质#xff1a; 在某个整数区间内#xff0c;存在某种性质使得区间内左半边的数都不满足该性质#xff1b;而右半边的数都满足该性…
有单调性的数列一定可以使用二分没有单调性的题目也可能可以使用二分 一整数二分
二分的本质 在某个整数区间内存在某种性质使得区间内左半边的数都不满足该性质而右半边的数都满足该性质那么二分的作用就是找到左右这两个分界点 1.找满足红色性质的边界点如图上 如果是让l等于mid即找左半边的分界点则要记得mid (lr1)/2 2.找满足绿色性质的边界点如图上 如果是让r等于mid即找右半边的分界点则mid (lr)/2不用另外加1
情况1为什么额外加1 答因为在程序中(lr)/2是向下取整当遇到遇到rl1l和r只相差1数组只有两个元素的情况(lr)/2就等于l这时候mid(lr)/2就是midl如下图所示这次循环相当于没有变化再次循环也不会有变化进入死循环 基本思想不断缩小答案区间当区间长度为一时就是答案
时间复杂度平均O(logn)
步骤 先写出基本模板:mid (lr)/2 定义判断条件check()函数 看应该是让lmid还是rmid如果应该lmid则把前面的mid改为 mid(lr1)/2
模板
// 检查x是否满足某种性质
private static boolean check(int x) { /* ... */
} // 区间[left, right]被划分成[left, mid]和[mid 1, right]时使用
// 或者称之为左二分查询查找左侧第一个满足条件的数
private static int leftBinarySearch(int[] arr, int left, int right) { while (left right) { int mid arr[left right 1]; if (check(mid)) { right mid; // check()判断mid是否满足性质 } else { left mid 1; } } return left;
} // 区间[left, right]被划分成[left, mid - 1]和[mid, right]时使用
// 或者称之为右二分查询查找右侧最后一个满足条件的数
private static int rightBinarySearch(int[] arr, int left, int right) { while (left right) { int mid arr[left right 1 1]; if (check(mid)) { left mid; // check()判断mid是否满足性质 } else { right mid - 1; // 有加必有减} } return left;
}
二浮点数二分
典型问题求一个数的平方根
基本思想不断缩小答案区间当区间长度足够小时即左右边界之差足够小边界的值就约等于答案
时间复杂度平均O(logn)
步骤 mid就等于(rl)/2; while循环判定条件为r-l1e-8左右边界之差足够小时结束循环
模板
// 检查x是否满足某种性质
private static boolean check(int x) { /* ... */
} // 区间[left, right]被划分成[left, mid]和[mid 1, right]时使用
// 或者称之为左二分查询查找左侧第一个满足条件的数
private static int leftBinarySearch(int[] arr, int left, int right) { while (left right) { int mid arr[left right 1]; if (check(mid)) { right mid; // check()判断mid是否满足性质 } else { left mid 1; } } return left;
} // 区间[left, right]被划分成[left, mid - 1]和[mid, right]时使用
// 或者称之为右二分查询查找右侧最后一个满足条件的数
private static int rightBinarySearch(int[] arr, int left, int right) { while (left right) { int mid arr[left right 1 1]; if (check(mid)) { left mid; // check()判断mid是否满足性质 } else { right mid - 1; // 有加必有减} } return left;
}注意点 使用二分一定可以找到一个满足条件的边界点不会出现无解的情况 整数二分中l和r表示的是区间左右边界的数组下标当遍历结束后lrarr[r] 就是所找的边界点 浮点数二分中l和r表示的不是数组下标而是左右边界本身 时间复杂度分析
二分查找Binary Search的时间复杂度分析如下
1. 最好情况Best Case
如果目标元素正好是数组的中间元素那么只需一次比较就能找到时间复杂度为
O(1)O(1)
2. 最坏情况Worst Case
每次查找都会将搜索范围缩小一半假设数组长度为 nn那么最多需要查找的次数是
T(n)T(n/2)O(1)T(n) T(n/2) O(1)
展开递归
T(n)T(n/4)O(1)O(1)T(n/8)O(1)O(1)O(1)…T(n) T(n/4) O(1) O(1) T(n/8) O(1) O(1) O(1) \dots
直到搜索范围缩小到 1即 n/2k1n/2^k 1解得
klog2nk \log_2 n
因此最坏情况下的时间复杂度是
O(logn)O(\log n)
3. 平均情况Average Case
在没有额外信息的情况下平均情况下也需要进行大约 O(logn) 级别的比较因此平均时间复杂度也是
O(logn)
总结
情况时间复杂度最好情况O(1)O(1)最坏情况O(logn)O(\log n)平均情况O(logn)O(\log n)
二分查找的时间复杂度远优于线性查找O(n)但前提是数据必须是有序的否则需要先进行排序如快速排序 O(nlogn)这会影响整体效率。
