一、通用模板，夹逼
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(nums==null||nums.length==0){return-1;}intstart=0;intend=nums.length-1;while(start+1<end){intmid=start+(end-start)/2;if(nums[mid]==target){returnmid;}elseif(nums[mid]<target){start=mid;}else{end=mid;}}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(nums==null||nums.length==0){return-1;}intstart=0,end=nums.length-1;while(start+1<end){//避免start=end=2^31 - 1时出现加法overflowintmid=start+(end-start)/2;// <，=，>的逻辑分开写，然后再看“=”能否并入其他分支if(nums[mid]<target){//不要管是mid+1还是mid-1，直接写midstart=mid;}elseif(nums[mid]==target){end=mid;}else{end=mid;}}//退出循环时，start，end相邻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.length==0){return-1;}intstart=0;intend=nums.length-1;intmid=-1;while(start+1<end){mid=start+(end-start)/2;if(nums[mid]==target){start=mid;}elseif(nums[mid]<target){start=mid;}else{end=mid;}}if(nums[end]==target){returnend;}if(nums[start]==target){returnstart;}return-1;}}二、识别OOXX模型，夹逼到中间的…OX…
在排序的数据集上进行二分
一般会给你一个数组
让你找数组中第一个/最后一个满足某个条件的位置
OOOOOOO…OO****XX….XXXXXX
2.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(a==null||a.length==0){returnnewint[]{};}intleft=0;intright=a.length-1;while(left+1<right){intmid=left+(right-left)/2;if(a[mid]==target){right=mid;}elseif(a[mid]<target){left=mid;}else{right=mid;}}int[]res=newint[k];for(inti=0;i<res.length;i++){if(left>=0&&right<=a.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(left>=0&&right>a.length-1){res[i]=a[left--];}elseif(left<0&&right<=a.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 hereintleft=0;intright=nums.length-1;while(left+1<right){intmid=left+(right-left)/2;if(nums[mid]<nums[mid+1]){left=mid;}else{right=mid;}}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 hereinttarget=nums[nums.length-1];intstart=0;intend=nums.length-1;intmid=-1;while(start+1<end){mid=start+(end-start)/2;if(nums[mid]<target){end=mid;}else{start=mid;}}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(a==null||a.length==0)return-1;intleft=0;intright=a.length-1;while(left+1<right){intmid=left+(right-left)/2;if(a[mid]>=a[left]){if(a[mid]>=target&&a[left]<=target){right=mid;}else{left=mid;}}else{if(a[mid]<=target&&a[right]>=target){left=mid;}else{right=mid;}}}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[P+1]，返回数组中任意一个峰值的位置。 数组保证至少存在一个峰 如果数组存在多个峰，返回其中任意一个就行 数组至少包含 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(a==null||a.length==0){return-1;}intleft=0;intright=a.length-1;while(left+1<right){intmid=left+(right-left)/2;if(a[mid]<a[mid+1]){left=mid;}else{right=mid;}}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(l==null||l.length==0){return0;}//最短锯木长度intleft=1;intright=0;for(inti=0;i<l.length;i++){if(l[i]>right){// 最长锯木长度right=l[i];}}while(left+1<right){intmid=left+(right-left)/2;//不同锯木长度能锯的个数nowK符合OOXX，找到最后一个OintnowK=testK(l,mid);if(nowK<k){right=mid;}elseif(nowK==k){left=mid;}else{left=mid;}}if(testK(l,right)>=k)returnright;if(testK(l,left)>=k)returnleft;return0;}privateinttestK(int[]l,intlength){intnowK=0;for(inti=0;i<l.length;i++){nowK+=l[i]/length;}returnnowK;}}4.2 华为机试-数据包分段传输的最小最大延迟
/** 在通信系统中，有一组数据包需要按顺序通过 k 个通道传输。每个数据包 i 的传输耗时为 nums[i]（单位：毫秒）。 传输规则： 第1点：同一通道内的数据包必须按顺序连续传输，即若数据包 [i, i+1, ..., j] 分配给同一通道，则该通道的传输总延迟为 nums[i] + nums[i+1] + ... + nums[j]。 第2点：不同通道之间可以并行传输，系统整体延迟取决于延迟最大的那个通道。 第3点：数据包只能被拆分为连续子段，例如 [1,2,3] 可以拆分为 [1,2]、[3]，不能拆分为 [1,3]、[2]。 任务：将 nums 数组划分到 k 个连续非空通道，使得传输总耗时最小。 输入描述 nums：非负整数数组，长度 n，1 <= 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){intused=1;longcur=0;// 给定上限 limit 后，贪心计算最少需要多少个连续通道。for(intx:nums){// 超过上限时必须切分到新通道。if(cur+x>limit){// 通道数不超过 k 说明上限可行，可以继续缩小答案。used++;cur=x;}else{cur+=x;}}returnused<=k;}publicstaticvoidmain(String[]args){// 读取数据包耗时数组和可用通道数 k。Scannersc=newScanner(System.in);String[]parts=sc.nextLine().trim().split(",");k=Integer.parseInt(sc.nextLine().trim());nums=newint[parts.length];longleft=0,right=0;for(inti=0;i<parts.length;i++){nums[i]=Integer.parseInt(parts[i].trim());left=Math.max(left,nums[i]);right+=nums[i];}while(left<right){longmid=(left+right)/2;if(ok(mid))right=mid;elseleft=mid+1;}// 二分结束时 left 就是最小可行最大延迟。System.out.println(left);}}
