D.二分查找－二分答案－求最大——2576. 求出最多标记下标

题目链接：2576. 求出最多标记下标（中等）

算法原理：

解法一：排序+双指针+贪心

33ms击败79.27%

时间复杂度O(Nlogn)

首先我们思考一件事情：当一个大的数遇到一堆小的数时，在同样满足2×小的数≤大的数的情况下，咱们选这些小的数中偏小的还是偏大的？那肯定选偏大的啊！因为偏小的可能还能与后续大的数再凑一对，这贪心的思想就来了

①我们要找大的数和小的数就要先排序

②从中间劈开，分别找满足题述条件的2*nums[i] <= nums[j]的数

如果当前的大数能跟前面小的数匹配上，ret+=2，left和right同时往后走

如果匹配不上，说明当前大数小了，要right往后走再继续匹配

解法二：二分查找

35ms击败43.90%

时间复杂度O(Nlogn)

①目标变量：对数

②目标条件：对数最多

③转换逻辑：在mid对的情况下能否满足2 * nums[i] <= nums[j]的条件

具体步骤：

①确定边界：

left：0，最少0对

right：n/2，n为数组长度，最多时，所有数都能组成一对

②确定二分模型：

由于要找最大对数，因此采用最右端点模型，如果没有mid对，说明mid太大了，属于最右端点的右边，需要返回true，缩小mid，向左调整

③check方法设计：判断方法跟解法一类似，都是贪心的思想，但不完全相同，如果数组长度为10，我们在找3对时，只需判断3个最大元素和3个最小元素能否配对即可，如果这都没有3对，那就更不可能再凑3对了

Java代码：

class Solution { //解法一：排序+双指针+贪心 public int maxNumOfMarkedIndices(int[] nums) { Arrays.sort(nums); int n=nums.length; int left=0,right=(n+1)/2; int ret=0; while(left<n/2&&right<n){ if(2*nums[left]<=nums[right]){ ret+=2; left++;right++; }else right++; } return ret; } }

class Solution { //解法二：二分查找 public int maxNumOfMarkedIndices(int[] nums) { Arrays.sort(nums); int n=nums.length; int left=0,right=n/2; int ret=0; while(left<right){ int mid=left+(right-left+1)/2; if(check(mid,nums)) right=mid-1; else left=mid; } return left*2; } //如果不能找到mid对则说明mid太大了，返回true，需要向左调整 private boolean check(int mid,int[] nums){ //0对一定可行，无需向更小调整 if(mid==0) return false; int n=nums.length; //贪心验证：前mid个最小元素配对最后mid个最大元素 for(int i=0;i<mid;i++) //有一个不满足，mid对就达不到 if(2*nums[i]>nums[n-mid+i]) return true; return false; } }