做logo的ppt模板下载网站,wordpress 示例页面 删除,wdcp 网站无法访问,室内设计培训班学费一般多少上篇文章讲动态规划获得了80k浏览#xff0c;这次的二分也值得你们一看#xff0c;这个系列是特别用心写的#xff0c;准备出书的哦 动态规划
3.0 引子
图书馆自习的时候,一女生背着一堆书进阅览室,结果警报响了,大妈让女生看是哪本书把警报弄响了#xff0c;女生把书倒出… 上篇文章讲动态规划获得了80k浏览这次的二分也值得你们一看这个系列是特别用心写的准备出书的哦 动态规划
3.0 引子
图书馆自习的时候,一女生背着一堆书进阅览室,结果警报响了,大妈让女生看是哪本书把警报弄响了女生把书倒出来一本一本的测。大妈见状急了把书分成两份,第一份过了一下,响了。又把这一份分成两份接着测三回就找到了大妈用鄙视的眼神看着女生仿佛在说 O(N)和 O(logN都分不清。
这就是二分法。欲知故事后续请继续往下看
3.1 经典二分问题
经典二分问题给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 。
写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。示例 1:
输入: nums [-1,0,3,5,9,12], target 9。输出: 4 解释: 9 出现在 nums 中并且下标为 4示例 2:
输入: nums [-1,0,3,5,9,12], target 2。输出: -1 解释: 2 不存在 nums 中因此返回 -1
思路1我们当然可以一个数一个数的遍历但是毫无疑问要被大妈鄙视这可怎么办呢
思路2二分查找 二分查找是一种基于比较目标值和数组中间元素的教科书式算法。
如果目标值等于中间元素则找到目标值。 如果目标值较小证明目标值小于中间元素及右边的元素继续在左侧搜索。 如果目标值较大证明目标值大于中间元素及左边的元素继续在右侧搜索。
算法代码描述
初始化指针 left 0, right n - 1。 当 left right 比较中间元素 nums[pivot] 和目标值 target 。 如果 target nums[pivot]返回 pivot。 如果 target nums[pivot]则在左侧继续搜索 right pivot - 1。 如果 target nums[pivot]则在右侧继续搜索 left pivot 1。
算法实现照例贴出三种语言的实现在Java实现中给出了详细注释
class Solution {public int search(int[] nums, int target) {//分别准备好左右端点int left 0, right nums.length - 1;//循环二分while (left right) {//取中点int pivot left (right - left) / 2;//找到答案并返回if (nums[pivot] target) return pivot;//向左继续找if (target nums[pivot]) right pivot - 1;//向右继续找else left pivot 1;}//未找到返回-1return -1;}
}
class Solution:def search(self, nums: List[int], target: int) - int:left, right 0, len(nums) - 1while left right:pivot left (right - left) // 2if nums[pivot] target:return pivotif target nums[pivot]:right pivot - 1else:left pivot 1return -1
class Solution {public:int search(vectorint nums, int target) {int pivot, left 0, right nums.size() - 1;while (left right) {pivot left (right - left) / 2;if (nums[pivot] target) return pivot;if (target nums[pivot]) right pivot - 1;else left pivot 1;}return -1;}
};
请记住这个代码因为整篇文章整个二分思想都和这段代码息息相关这也是最基础的二分问题。
3.2 基础二分小变形1
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。
思路我们注意这一题和上一题的区别在于这一题并不存在‘没找到’这种情况因为要插入到”第一个比目标值大的数“的左边返回这样一个插入位置你不可能”找不到“不可返回-1。
事实上我们的目标也再不是找到一个相同的数字而是找到第一个比目标值大的数也就是插入位置。 而我们第一段代码的返回答案也可以省略了代码的内部逻辑是”一路找到最后返回的一定是答案“而上段代码的逻辑是”边找边判断找到最后还没有找到就返回-1“。
下面是代码
public class Solution {public int searchInsert(int[] nums, int target) {int len nums.length;int left 0;int right len - 1;while (left right) {int mid (left right) / 2;if (nums[mid] target) {left mid 1;} else {right mid - 1;}}return left;}
}
提醒所以如果你是一个想注重细节做到写二分代码不出错那么你就需要关心最后返回值while结束条件while内部是否加判断等等这些细节了。
3.3基础二分小变形2
给定一个按照升序排列的整数数组 nums和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值返回 [-1, -1]。
示例 1:输入: nums [5,7,7,8,8,10], target 8输出: [3,4] 示例 2:输入: nums [5,7,7,8,8,10], target 6输出: [-1,-1]
思路两个二分稍微改一下就可以找到第一个target或最后一个target
本元素和前面一个元素不相等才代表找到了最左边的目标元素。
本元素和后面一个元素不相等才代表找到了最右边的目标元素。
class Solution {public int[] searchRange(int[] nums, int target) {int[] ansnew int[2];ans[0]searchRangeLeft(nums,target);ans[1]searchRangeRight(nums,target);return ans;}public int searchRangeLeft(int[] nums, int target) {int left0;int rightnums.length-1;while(leftright){int mid(leftright)/2;if(nums[mid]target){rightmid-1;}else if(nums[mid]target){leftmid1;}else if(mid0 || nums[mid-1]!target){return mid;}else{rightmid-1;}}return -1;}public int searchRangeRight(int[] nums, int target) {int left0;int rightnums.length-1;while(leftright){int mid(leftright)/2;if(nums[mid]target){rightmid-1;}else if(nums[mid]target){leftmid1;}else if(midnums.length-1 || nums[mid1]!target){return mid;}else{leftmid1;}}return -1;}
}
注意如果你找到一个target然后向左向右线性查找是不对的这样时间会退化为O(N)和二分的本意违背了。
3.4泛化二分的概念
看到第一节可能大部分人都没有问题
看到第二节可能对有些写二分总有bug的同学有一些帮助会觉得”细节确实需要注意“二分查找从此要一次就bug free
至此我们看一下百度百科对二分的定义 简单来说我们介绍的就是在顺序存储结构数组有序的情况下进行二分查找。
从第四节开始我们介绍的就不是传统意义上的二分查找了不局限于”有序“甚至不局限于线性结构while循环里判断向左还是向右搜索的条件也不会这么单一而更可能是这样 while (范围没有缩小为0) { if (满足某种条件) { 排除一半答案 } else { 排除另一半答案 } }
我们的思想是只要可以通过正确逻辑用二分思想正确的缩小查找范围都称之为二分。
下面就来体会一下什么是二分思想
我们正在玩一个猜数字游戏。 游戏规则如下 我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。 每次你猜错了我会告诉你这个数字是大了还是小了。你调用一个预先定义好的接口 guess(int num)它会返回 3 个可能的结果-11 或 0
-1 : 我的数字比较小 1 : 我的数字比较大 0 : 恭喜你猜对了 示例 :
输入: n 10, pick 6输出: 6
/* The guess API is defined in the parent class GuessGame.param num, your guessreturn -1 if my number is lower, 1 if my number is higher, otherwise return 0int guess(int num); */public class Solution extends GuessGame {public int guessNumber(int n) {int low 1;int high n;while (low high) {int mid low (high - low) / 2;int res guess(mid);if (res 0)return mid;else if (res 0)high mid - 1;elselow mid 1;}return -1;}
}
你看这就是把条件抽象成一个接口完全脱离了线性数据结构更和有序无序没关系只是二分的思想。
3.5在线性结构上二分的题目积累
例1
峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums其中 nums[i] ≠ nums[i1]找到峰值元素并返回其索引。
数组可能包含多个峰值在这种情况下返回任何一个峰值所在位置即可。
你可以假设 nums[-1] nums[n] -∞。
示例 1:输入: nums [1,2,3,1]输出: 2 解释: 3 是峰值元素你的函数应该返回其索引 2。 示例 2:输入: nums [1,2,1,3,5,6,4]输出: 1 或 5 解释: 你的函数可以返回索引 1其峰值元素为 2 或者返回索引 5 其峰值元素为 6。说明:你的解法应该是 O(logN) 时间复杂度的。
思路
可以用二分的要求线性表能够根据中间元素的特点推测它两侧元素的性质以达到缩减问题规模的效果即可不一定非要有序
具体到本题来说我们如何做到搜索到任何一个“峰值”呢请看图 要先有上升的趋势后有下降的趋势。更通俗一点就是说要保证前一个数字比峰值小后一个数字比峰值大我们只要每次搜索都满足这个条件搜到最后就一定可以找到某个峰值因为从递增到递减肯定是因为中间有峰值的存在所导致的。 我们看中点如果中点向右有递增趋势我们就继续搜索右边 反之有向左递增的趋势我们就搜左边 下面给出代码
public class Solution {public int findPeakElement(int[] nums) {int l 0, r nums.length - 1;while (l r) {int mid (l r) / 2;if (nums[mid] nums[mid 1])r mid;elsel mid 1;}return l;}
}
我们发现这个题目的代码逻辑就是第二节的”一路找到最后返回的一定是答案“不同于最基础的二分”边找边判断找到最后还没有找到就返回-1“。我们是缩小范围到最后找到了答案l。
例2
假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]输出: 1 示例 2:
输入: [4,5,6,7,0,1,2]输出: 0
分析
如果数组没有翻转即 nums[left] nums[right]则 nums[left] 就是最小值直接返回。
如果数组翻转需要找到数组中第二部分的第一个元素
。
下面讨论数组翻转的情况下如何收缩区间以找到这个元素
若 nums[left] nums[mid]说明区间 [left,mid] 连续递增则最小元素一定不在这个区间里可以直接排除。因此令 left mid1在 [mid1,right] 继续查找。 否则说明区间 [left,mid] 不连续则最小元素一定在这个区间里。因此令 right mid在 [left,mid] 继续查找 [left,right] 表示当前搜索的区间。
注意 right 更新时会被设为 mid 而不是 mid-1因为 mid 无法被排除。
class Solution {public int findMin(int[] nums) {if(nums.length1)return nums[0];if(nums[0]nums[nums.length-1])return nums[0];int left0;int rightnums.length-1;int mid0;while(leftright){mid(leftright)/2;if(nums[mid]nums[0]){leftmid1;}else{rightmid;}}return nums[right];}
}
例3其它条件和例2一样例3要搜索一个给定的目标值如果数组中存在这个目标值则返回它的索引否则返回 -1 。
思路请先自行思考
先通过例2的方法找到分割点再对左右某一边进行二分即可代码请自行书写。
3.6二维数组的二分查找
编写一个高效的算法来判断 m x n 矩阵中是否存在一个目标值。该矩阵具有如下特性
每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。示例 1: matrix [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target 3 输出: true示例 2: matrix [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target 13 输出: false
仔细观察我们发现其实这个二维数组整体就是有序的所以当成一维数组二分查找即可但是要注意二维数组的操作需要一点功底。
class Solution {public boolean searchMatrix(int[][] matrix, int target) {if (matrix null || matrix.length 0) {return false;}int row matrix.length;int col matrix[0].length;int start 0;int end row * col - 1;while (start end) {int mid start (end - start) / 2;if (matrix[mid / col][mid % col] target)return true;else if (matrix[mid / col][mid % col] target)end mid - 1;else start mid 1;}return false;}
}
注意这里有个细节正规的二分其实都应该这么写之前的写法可能会溢出。
3.7二叉树上二分的题目积累
我们刚才学会了一些一维二维数组的二分操作下面我们再去其它数据结构试试看继续养成二分的思想。
例1先看一道简单的在二叉树上查找值。
给定一个不为空的二叉搜索树和一个目标值 target请在该二叉搜索树中找到最接近目标值 target 的数值。
注意
给定的目标值 target 是一个浮点数题目保证在该二叉搜索树中只会存在一个最接近目标值的数。 示例
输入: root [4,2,5,1,3]目标值 target 3.714286 4 / \ 2 5 / \ 1 3
输出: 4
思路二分当前节点比target大就往左边搜因为右边的差距更大当前节点比target小就往右搜因为左边的差距更大。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {public int closestValue(TreeNode root, double target) {int val, closest root.val;while (root ! null) {val root.val;closest Math.abs(val - target) Math.abs(closest - target) ? val : closest;root target root.val ? root.left : root.right;}return closest;}
}
例2
给出一个完全二叉树求出该树的节点个数。
说明
完全二叉树的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1~ 2h 个节点。
示例:
输入: 1 / \ 2 3 / \ / 4 5 6
输出: 6
思路如果不考虑最后一层节点数完全可以算出来每一层分别为1248....你会发现是2的n次方那么总和也很好求所以问题就在于如何知道最后一层有多少节点换句话说最后一层的最右边的那个节点在哪里我们需要二分搜索。 目标找箭头指向的结点。
我们采用二分法
1找到右子树的最左结点 我们知道总深度为4如果右子树深度为34-1说明图中最后的1是存在的说明最后一行最右结点一定来自右子树否则如果我们修改一下如下图 右子树深度为24-1不存在最后一行的结点。说明最后一行最右结点一定来自左子树.
2判断之后如果是这种情况我们排除了左子树计算排除的结点个数并对右子树如图2做相同的处理。 更新结点数未被框起的部分满二叉树公式11是根结点
3对方框内重复此过程。 我们继续看右子树发现右子树深度为13-1.
说明最深层最右结点来自于左子树。所以对左子树重复上述过程 我们发现右子树深度12整棵树深度-1说明最深层最右结点来自于右子树所以对右子树重复此过程。
最终找到它。
public class Demo {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value data;}}
//返回结点个数public static int nodeNum(Node head) {if (head null) {return 0;}return bs(head, 1, mostLeftLevel(head, 1));}
//返回根为node当前层数为l总深度为h的结点个数public static int bs(Node node, int l, int h) {if (l h) {return 1;}if (mostLeftLevel(node.right, l 1) h) { //右子树最深一行最左为空return (1 (h - l)) bs(node.right, l 1, h); //右bs左子树结点个数} else { //右子树最深一行最左不为空return (1 (h - l - 1)) bs(node.left, l 1, h);//左bs右子树结点个数}}
//计算树的高度public static int mostLeftLevel(Node node, int level) {while (node ! null) {level;node node.left;}return level - 1;}public static void main(String[] args) {Node head new Node(1);head.left new Node(2);head.right new Node(3);head.left.left new Node(4);head.left.right new Node(5);head.right.left new Node(6);System.out.println(nodeNum(head));}
}
我们再回忆第4节泛化概念时给的伪代码 while (范围没有缩小为0) { if (满足某种条件) { 排除一半答案 } else { 排除另一半答案 } }
其实真的就是这样的一个终止条件本题就是lh一个if判断条件本题就是mostLeftLevel(node.right, l 1) h注意细节就可以进行各种广义的二分啦。 3.8数学中的二分
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根其中 x 是非负整数。
由于返回类型是整数结果只保留整数的部分小数部分将被舍去。
示例 1:
输入: 4输出: 2 示例 2:
输入: 8输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数小数部分将被舍去。 思路依旧是二分格式和上文都一样。
public class Solution {public int mySqrt(int x) {long left 0;long right Integer.MAX_VALUE;while (left right) {long mid (left right 1) 1;long square mid * mid;if (square x) {right mid - 1;} else {left mid;}}return (int) left;}
} 3.9最大化或最小化问题
如果在求解最大最小问题中能比较简单的判断某个解是否满足条件这里的简单一般指的是o(n)及以下视具体数据范围而定使用二分搜索答案就能很好的解决问题。
举个例子POJ1064
题目链接http://poj.org/problem?id1064
题目大意有n条绳子长度分别为L[i]。如果从他们中切割出k条长度相同的绳子的话这k条绳子每条最长能有多长答案保留小数点后两位规定1单位长度的绳子最多可以切割成100份。
思路二分搜索答案每条最短0最大设置一个较大的数然后开始二分答案并依次判断判断也很简单判断每个绳子的长度整除答案的累加和是不是大于k就好了。 #include cstdio
#include cmath
using namespace std;
const int M10005;
const double inf200005.0;
double L[M];
int n,k;
bool judge(double x)//判断解是否可行
{int num0;for(int i0;in;i)num(int)(L[i]/x);return numk;
}
void solve()//二分答案
{double left0,rightinf;for(int i0;i100;i) //代替while(rl) 避免了精度问题{ //1次循环可以把区间缩小一半100次可以达到10^(-30)的精度double mid(leftright)/2;if(judge(mid)) leftmid;else rightmid;}printf(%.2f\n,floor(right*100)/100);
}
int main()
{while(scanf(%d%d,n,k)!-1){for(int i0;in;i)scanf(%lf,L[i]);solve();}
}
POJ2456
题意
有n个牛栏选m个放进牛相当于一条线段上有 n 个点选取 m 个点
使得相邻点之间的最小距离值最大
思路和上一道题类似二分答案判断答案也很简单贪心即可遍历遇到大于枚举的距离就放一只牛看最后能不能放得下。
3.10总结
其实还有一些用到二分的比如最大化平均值问题但是由于篇幅和大部分读者水平和时间有限暂时不写了如果有时间还是会持续更新
