算法-二分法

一、通用模板夹逼1.1 任意位置/**457 · 经典二分查找问题 描述 在一个排序数组中找一个数返回该数出现的任意位置如果不存在返回 -1。 样例 样例 1 输入nums [1,2,2,4,5,5], target 2 输出1 或者 2 样例 2 输入nums [1,2,2,4,5,5], target 6 输出-1*/publicclassSolution{/** * param nums: An integer array sorted in ascending order * param target: An integer * return: An integer */publicintfindPosition(int[]nums,inttarget){// write your code hereif(numsnull||nums.length0){return-1;}intstart0;intendnums.length-1;while(start1end){intmidstart(end-start)/2;if(nums[mid]target){returnmid;}elseif(nums[mid]target){startmid;}else{endmid;}}if(nums[start]target)returnstart;if(nums[end]target)returnend;return-1;}}1.2 第一个位置/**14 · 二分查找 描述 给定一个排序的整数数组升序和一个要查找的整数 target用O(logn)的时间查找到 target 第一次出现的下标从 0 开始如果 target 不存在于数组中返回 -1。 样例 样例 1 输入 数组 [1,4,4,5,7,7,8,9,9,10] target 1 输出 0 解释 第一次出现在第0个位置。 样例 2 输入 数组 [1, 2, 3, 3, 4, 5, 10] target 3 输出 2 解释 第一次出现在第2个位置 样例 3 输入 数组 [1, 2, 3, 3, 4, 5, 10] target 6 输出 -1 解释 没有出现过6 返回-1*/publicclassSolution{/** * param nums: The integer array. * param target: Target to find. * return: The first position of target. Position starts from 0. */publicintbinarySearch(int[]nums,inttarget){if(numsnull||nums.length0){return-1;}intstart0,endnums.length-1;while(start1end){//避免startend2^31 - 1时出现加法overflowintmidstart(end-start)/2;// 的逻辑分开写然后再看“”能否并入其他分支if(nums[mid]target){//不要管是mid1还是mid-1直接写midstartmid;}elseif(nums[mid]target){endmid;}else{endmid;}}//退出循环时startend相邻if(nums[start]target){returnstart;}if(nums[end]target){returnend;}return-1;}}1.3 最后一个位置/**给一个升序数组找到 target 最后一次出现的位置如果没出现过返回 -1 样例 样例 1 输入nums [1,2,2,4,5,5], target 2 输出2 样例 2 输入nums [1,2,2,4,5,5], target 6 输出-1*/publicclassSolution{/** * param nums: An integer array sorted in ascending order * param target: An integer * return: An integer */publicintlastPosition(int[]nums,inttarget){// write your code hereif(nums.length0){return-1;}intstart0;intendnums.length-1;intmid-1;while(start1end){midstart(end-start)/2;if(nums[mid]target){startmid;}elseif(nums[mid]target){startmid;}else{endmid;}}if(nums[end]target){returnend;}if(nums[start]target){returnstart;}return-1;}}二、识别OOXX模型夹逼到中间的…OX…在排序的数据集上进行二分一般会给你一个数组让你找数组中第一个/最后一个满足某个条件的位置OOOOOOO…OO****XX….XXXXXX2.1 Find K Closest Elements/**描述 给一个目标数 target, 一个非负整数 k, 一个按照升序排列的数组 A。在A中找与target最接近的k个整数。返回这k个数并按照与target的接近程度从小到大排序如果接近程度相当那么小的数排在前面。 k是一个非负整数并且不大于已排序数组的长度。 给定数组的长度是正整数, 不会超过 10^4 数组中元素的绝对值不会超过 10^4 样例 样例 1: 输入: A [1, 2, 3], target 2, k 3 输出: [2, 1, 3] 样例 2: 输入: A [1, 4, 6, 8], target 3, k 3 输出: [4, 1, 6]*/publicclassSolution{/** * param a: an integer array * param target: An integer * param k: An integer * return: an integer array */publicint[]kClosestNumbers(int[]a,inttarget,intk){// write your code hereif(anull||a.length0){returnnewint[]{};}intleft0;intrighta.length-1;while(left1right){intmidleft(right-left)/2;if(a[mid]target){rightmid;}elseif(a[mid]target){leftmid;}else{rightmid;}}int[]resnewint[k];for(inti0;ires.length;i){if(left0righta.length-1){if(Math.abs(a[left]-target)Math.abs(a[right]-target)){res[i]a[left];left--;}else{res[i]a[right];right;}}elseif(left0righta.length-1){res[i]a[left--];}elseif(left0righta.length-1){res[i]a[right];}}returnres;}}2.2 Maximum Number in Mountain Sequence/**描述 给 n 个整数的山脉数组即先增后减的序列找到山顶最大值。 数组严格递增严格递减 样例 例1: 输入: nums [1, 2, 4, 8, 6, 3] 输出: 8 例2: 输入: nums [10, 9, 8, 7], 输出: 10*/publicclassSolution{/** * param nums: a mountain sequence which increase firstly and then decrease * return: then mountain top */publicintmountainSequence(int[]nums){// write your code hereintleft0;intrightnums.length-1;while(left1right){intmidleft(right-left)/2;if(nums[mid]nums[mid1]){leftmid;}else{rightmid;}}returnMath.max(nums[left],nums[right]);}}2.3 Find Minimum in Rotated Sorted Array建立OOXX模型将左半边有序数组看做O, 将右半边有序数组看做X可以把最后一个数当成target找最后一个小于等于target的位置/**描述 假设一个按升序排好序的数组在其某一未知点发生了旋转比如0 1 2 4 5 6 7 可能变成4 5 6 7 0 1 2。你需要找到其中最小的元素。 你可以假设数组中不存在重复元素。 样例 样例 1: 输入[4, 5, 6, 7, 0, 1, 2] 输出0 解释 数组中的最小值为0 样例 2: 输入[2,1] 输出1 解释 数组中的最小值为1*/publicclassSolution{/** * param nums: a rotated sorted array * return: the minimum number in the array */publicintfindMin(int[]nums){// write your code hereinttargetnums[nums.length-1];intstart0;intendnums.length-1;intmid-1;while(start1end){midstart(end-start)/2;if(nums[mid]target){endmid;}else{startmid;}}if(nums[start]target){returnnums[start];}returnnums[end];}}2.4 Search in Rotated Sorted Array在一个Rotated Sorted Array上切一刀可以判断出这一刀切在左半部分还是右半部分这一刀的两边仍然是Rotated Sorted Array/**描述 给定一个有序数组但是数组以某个元素作为支点进行了旋转(比如0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值target进行搜索如果在数组中找到目标值返回数组中的索引位置否则返回-1。你可以假设数组中不存在重复的元素。 样例 样例 1 输入 数组 [4, 5, 1, 2, 3] target 1 输出 2 解释 1在数组中对应索引位置为2。 样例 2 输入 数组 [4, 5, 1, 2, 3] target 0 输出 -1 解释 0不在数组中返回-1。*/publicclassSolution{/** * param a: an integer rotated sorted array * param target: an integer to be searched * return: an integer */publicintsearch(int[]a,inttarget){// write your code hereif(anull||a.length0)return-1;intleft0;intrighta.length-1;while(left1right){intmidleft(right-left)/2;if(a[mid]a[left]){if(a[mid]targeta[left]target){rightmid;}else{leftmid;}}else{if(a[mid]targeta[right]target){leftmid;}else{rightmid;}}}if(a[left]target)returnleft;if(a[right]target)returnright;return-1;}}三、在未排序的且无法排序的数据集上进行二分并无法找到一个条件形成 XXOO 的模型但可以根据判断保留下有解的那一半或者去掉无解的一半3.1 Find Peak Element/**描述 给定一个整数数组(size为n)其具有以下特点 相邻位置的数字是不同的 A[0] A[1] 并且 A[n - 2] A[n - 1] 假定P是峰值的位置则满足A[P] A[P-1]且A[P] A[P1]返回数组中任意一个峰值的位置。 数组保证至少存在一个峰 如果数组存在多个峰返回其中任意一个就行 数组至少包含 3 个数 样例 样例 1 输入 A [1, 2, 1, 3, 4, 5, 7, 6] 输出 1 解释 返回任意一个峰顶元素的下标6也同样正确。 样例 2 输入 A [1,2,3,4,1] 输出 3 解释 返回峰顶元素的下标。*/publicclassSolution{/** * param a: An integers array. * return: return any of peek positions. */publicintfindPeak(int[]a){// write your code hereif(anull||a.length0){return-1;}intleft0;intrighta.length-1;while(left1right){intmidleft(right-left)/2;if(a[mid]a[mid1]){leftmid;}else{rightmid;}}if(a[left]a[right]){returnleft;}else{returnright;}}}四、在答案集上进行二分第一步确定答案范围第二步验证答案大小4.1 Wood Cut/**描述 有一些原木现在想把这些木头切割成一些长度相同的小段木头需要得到的小段的数目至少为 k。给定L和k你需要计算能够得到的小段木头的最大长度。 木头长度的单位是厘米。原木的长度都是正整数我们要求切割得到的小段木头的长度也要求是整数。无法切出要求至少 k 段的,则返回 0 即可。 样例 样例 1 输入: L [232, 124, 456] k 7 输出: 114 说明: 我们可以把它分成 114 的 7 段而 115 不可以 而且对于 124 这根原木来说多余的部分没用可以舍弃不需要完整利用 样例 2 输入: L [1, 2, 3] k 7 输出: 0 说明: 很显然我们不能按照题目要求完成。*/publicclassSolution{/** * param l: Given n pieces of wood with length L[i] * param k: An integer * return: The maximum length of the small pieces */publicintwoodCut(int[]l,intk){// write your code hereif(lnull||l.length0){return0;}//最短锯木长度intleft1;intright0;for(inti0;il.length;i){if(l[i]right){// 最长锯木长度rightl[i];}}while(left1right){intmidleft(right-left)/2;//不同锯木长度能锯的个数nowK符合OOXX找到最后一个OintnowKtestK(l,mid);if(nowKk){rightmid;}elseif(nowKk){leftmid;}else{leftmid;}}if(testK(l,right)k)returnright;if(testK(l,left)k)returnleft;return0;}privateinttestK(int[]l,intlength){intnowK0;for(inti0;il.length;i){nowKl[i]/length;}returnnowK;}}4.2 华为机试-数据包分段传输的最小最大延迟/** 在通信系统中有一组数据包需要按顺序通过 k 个通道传输。每个数据包 i 的传输耗时为 nums[i]单位毫秒。 传输规则 第1点同一通道内的数据包必须按顺序连续传输即若数据包 [i, i1, ..., j] 分配给同一通道则该通道的传输总延迟为 nums[i] nums[i1] ... nums[j]。 第2点不同通道之间可以并行传输系统整体延迟取决于延迟最大的那个通道。 第3点数据包只能被拆分为连续子段例如 [1,2,3] 可以拆分为 [1,2]、[3]不能拆分为 [1,3]、[2]。 任务将 nums 数组划分到 k 个连续非空通道使得传输总耗时最小。 输入描述 nums非负整数数组长度 n1 n 1000每个元素满足 0 nums[j] 10^6。 k整数通道数量1 k n。 输入分两行 nums k 输出描述 返回一个整数表示符合题意的最优传输策略下的总耗时。 样例 1 输入 7,2,5,10,8 2 输出 18 说明划分为 [7,2,5] 和 [10,8] 时两个通道耗时分别为 14 和 18最大值为 18是所有划分中的最小最大延迟。 样例 2 输入 1,2,3,4,5 2 输出 9 说明最优划分为 [1,2,3] 和 [4,5]总耗时为 9。 样例 3 输入 1,4,4 3 输出 4 说明划分为 [1]、[4]、[4]最优总耗时为 4。 *//** 思路 二分法 把最终答案看成一个最大延迟上限。给定某个上限后从左到右尽量把数据包放进当前通道如果加入当前包会超过上限就新开一个通道。 这样得到的是该上限下所需的最少通道数。若通道数不超过 k说明上限可行可以继续尝试更小值否则需要增大上限。 答案在“最大单个包耗时”和“全部包耗时之和”之间二分。 */importjava.util.*;publicclassMain{staticint[]nums;staticintk;staticbooleanok(longlimit){intused1;longcur0;// 给定上限 limit 后贪心计算最少需要多少个连续通道。for(intx:nums){// 超过上限时必须切分到新通道。if(curxlimit){// 通道数不超过 k 说明上限可行可以继续缩小答案。used;curx;}else{curx;}}returnusedk;}publicstaticvoidmain(String[]args){// 读取数据包耗时数组和可用通道数 k。ScannerscnewScanner(System.in);String[]partssc.nextLine().trim().split(,);kInteger.parseInt(sc.nextLine().trim());numsnewint[parts.length];longleft0,right0;for(inti0;iparts.length;i){nums[i]Integer.parseInt(parts[i].trim());leftMath.max(left,nums[i]);rightnums[i];}while(leftright){longmid(leftright)/2;if(ok(mid))rightmid;elseleftmid1;}// 二分结束时 left 就是最小可行最大延迟。System.out.println(left);}}