LC：二分查找——杂记

268. 丢失的数字

LC将此题归类为二分查找，并且为简单题，下面记一下自己对这道题目的思考。
题目链接：268.丢失的数字


第一次看到这个题目，虽然标注的为简单，但肯定不能直接排序或者使用哈希表去实现，如果这样做的话这道题目就没有任何意义。我首先联想到一道剑指offer上面的一道原地哈希的题目，但具体写的时候下笔难。
下面参考宫水三叶的题解，自己重新写一遍。
方法一：原地哈希：
由于题目所述为查找nums[]一共n个数，[0, n]这n + 1个数哪个不存在与数组中。借助nums本体数组，使用原地哈希，每次碰到一个数字，如果不符合nums[i] == i，此时将nums[i]移动到对应numsp[i]的位置上，继续从i开始遍历。
第一遍遍历完成后，再此遍历nums数组，如果碰到nums[i] != i 此时直接返回 i ，否则遍历完毕仍然没有遇到符合要求的数，此时直接返回n。
代码如下所示：

class Solution {public int missingNumber(int[] nums) {// 原地交换int n = nums.length;for(int i = 0; i < n; i++){if(nums[i] != i && nums[i] < n){// 这里为什么要i--，因为这个交换操作只是将nums[i]对应的元素移到了它应该处于的位置nums[i]上，//但原本nums[i]位置的数组却被交换到i位置了，下次遍历需要继续从i位置开始遍历，由于for循环中对i不断++所以这里需要进行-1操作。swap(nums, nums[i], i--);}}for(int i = 0; i < n; i++){if(nums[i] != i){return i;}}return n;}public void swap(int[] nums, int i, int j){int num = nums[i];nums[i] = nums[j];nums[j] = num;}
}

方法二：异或操作：
如果做过：【只有一个数字出现1次，其他数字都出现两次】这个题目，相信也可以对题目稍加改造，将其构造为这个题目，具体操作，首先将ans 异或[0, n]随后，遍历nums数组并对ans进行异或操作。这样处理后，最终的ans就是返回答案。

class Solution {public int missingNumber(int[] nums) {//异或int ans = 0, n = nums.length;for(int i = 0; i <= n; i++){ans ^= i;}for(int i = 0; i < n; i++){ans ^= nums[i];}return ans;}
}

方法三：等差数组求和：
由于题目所述为寻找[0, n] 这n + 1个数字在nums中没有出现的数字，先对[0, n]这n + 1个数字使用等差数列求和，计为sum。再遍历nums，对nums中所有数组求和curSum，随后sum - curSum即为最终答案。

代码：

class Solution {public int missingNumber(int[] nums) {int n = nums.length;int curSum = 0, sum = n * (n + 1) / 2;for(int num : nums){curSum += num;}return sum - curSum;}}

162. 寻找峰值

题目链接：162.寻找峰值

这个题目散发出熟悉的味道，之前做过，并且也成功做出来了，但是这次没看题解代码写的比别人题解非常负责，具体可以参考后面写的代码示例。
基本思想：使用二分查找思想，[l, r] 求的mid后，比较nums[mid] 和 nums[mid + 1]的大小关系。（为什么比较nums[mid] 和 nums[mid + 1]而不是比较nums[mid] 和 nums[mid - 1]的大小：Java中向下取整的，保证有两个数的前提下，通过(l + r) / 2 计算出的mid，此时mid + 1一定不会越界的，相反对于mid - 1可能会越界，在只有两个数的情况下就会越界。）
随后根据nums[mid] 和 nums[mid + 1]的大小关系移动左右边界。

1. nums[mid] > nums[mid + 1] 此时，mid可以用，并且由于左边数更大，所以边界向左边收缩。r = mid。
2. 不满足1，此时mid 是不可用的，此时向右边界收缩，r = mid + 1。

上面思路的前提，nums[-1] == nums[n] = -00。

代码展示：

class Solution {public int findPeakElement(int[] nums) {int len = nums.length;if(len == 1)    return 0;int l = 0, r = len - 1;while(l < r){int mid = l + (r - l) / 2;if((mid == 0 && nums[mid] > nums[mid + 1]) || (mid == len - 1 && nums[mid] > nums[mid - 1])){return mid;}if(mid > 0 && mid < len - 1 && nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]){return mid;}if(nums[mid] > nums[mid + 1]){r = mid - 1;}else{l = mid + 1;}}return l;}
}// 之前参考题解的代码：
class Solution {public int findPeakElement(int[] nums) {int left = 0, right = nums.length - 1;while(left < right){int mid = (left + right) / 2;if(nums[mid] > nums[mid + 1]){right = mid;}else{left = mid + 1;}}return left;}
}

436. 寻找右区间

题目链接：436.寻找右区间

初次看到这个题目，题目没有读懂，不知道题目需要的是什么东西。后面继续看才理解，题目讲述的返回数组的规则。
上述题目中有一个重要信息：每个starti都不相同。
我的思路：

1. 首先构建一个HashMap用以保存start[i][0] 和下标 i 的对应关系，为什么需要保存这个对应关系，因为后续需要对数组intervals进行排序，此时对应下标关系就乱了，因此首先保存对应下标关系。如果题目中没有说明 start[i] 都不相同，此时如何做，仍然是使用哈希表，此时键key设置的hash(intervals[i][0], intervals[i][1])。
2. 对intervals[i] 按照starti升序排列。
3. 遍历每个intervals[i][1] ，使用二分查找找对应的右区间。

最终代码如下：

// 不完全二分查找
class Solution {public int[] findRightInterval(int[][] intervals) {int len = intervals.length;Map<Integer, Integer> map = new HashMap<>();for(int i = 0; i < len; i++){map.put(intervals[i][0], i);}Arrays.sort(intervals, (a, b)->a[0] - b[0]);int[] ans = new int[len];Arrays.fill(ans, -1);for(int i = 0; i < len; i++){if(intervals[i][1] > intervals[len - 1][0]){continue;}int search = binearySearch(intervals, intervals[i][1], map);ans[map.get(intervals[i][0])] = search;}return ans;}public int binearySearch(int[][] intervals, int num, Map<Integer, Integer> map){int l = 0, r = intervals.length;while(l < r){int mid = l + (r - l) / 2;if(intervals[mid][0] < num){l = mid + 1;}else{r = mid;}}return map.get(intervals[l][0]);}
}// 完全二分查找、不进行先验判断class Solution {public int[] findRightInterval(int[][] intervals) {int len = intervals.length;Map<Integer, Integer> map = new HashMap<>();for(int i = 0; i < len; i++){map.put(intervals[i][0], i);}Arrays.sort(intervals, (a, b)->a[0] - b[0]);int[] ans = new int[len];for(int i = 0; i < len; i++){int search = binearySearch(intervals, intervals[i][1]);ans[map.get(intervals[i][0])] = search < len ? map.get(intervals[search][0]): -1;}return ans;}public int binearySearch(int[][] intervals, int num){int l = 0, r = intervals.length;while(l < r){int mid = l + (r - l) / 2;if(intervals[mid][0] < num){l = mid + 1;}else{r = mid;}}return l;}
}