【leetcode题解】二分算法
目录
二分查找
在排序数组中查找元素的第一个和最后一个位置
总结二分模板
x 的平方根
搜索插入位置
山脉数组的峰顶索引
寻找峰值
寻找旋转排序数组中的最小值
0~n-1中缺失的数字
二分查找
二分查找算法
适用于数组有序的时候（×）
模板：
1. 朴素的二分模板 （easy->局限）
2. 查找左边界的二分模板 （万能，细节多）
3. 查找右边界的二分模板 （万能，细节多）
朴素二分模板：
while(left<=right){
int mid=left+(right-left)/2;
if(...) left=mid+1;
else if(...) right=mid-1;
else return ...;
}704. 二分查找 - 力扣（LeetCode）
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
else
return mid;
}
return -1;
}
}查找区间左端点细节处理：
1. 循环条件：left=right的时候，就是最终结果，无需判断；如果判断就会死循环
2. 求中点的操作：Ⅰ.left+(right-left)/2 Ⅱ.left+(right-left+1)/2;（死循环）
查找区间右端点细节处理：
1. 循环条件：left=right的时候，就是最终结果，无需判断；如果判断就会死循环
2. 求中点的操作：Ⅰ.left+(right-left)/2 （死循环）Ⅱ.left+(right-left+1)/2;
总结模板：
查找区间左端点的模板：
while(left<right){
int mid=left+(right-left)/2;
if(...) left=mid+1;
else right=mid;
}
查找区间右端点的模板：
while(left<right){
int mid=left+(right-left+1)/2;
if(...) left=mid;
else right=mid-1;
}
在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
解法一：暴力查找
解法二：朴素二分
查找区间左端点解题思路：
x<t时left=mid+1
x≥t时right=mid
查找区间左端点细节处理：
1. 循环条件为left<right，而不是left≤right（left=right的时候，就是最终结果，无需判断，若判断，则死循环）
2. 求中点的操作：left+(right-left)/2若使用left+(right-left+1)/2则死循环
查找区间右端点解题思路：
x<t时left=mid
x≥t时right=mid-1
查找区间右端点细节处理：
1. 循环条件为left<right，而不是left≤right（left=right的时候，就是最终结果，无需判断，若判断，则死循环）
2. 求中点的操作：left+(right-left+1)/2若使用left+(right-left)/2则死循环
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ret = new int[2];
ret[0] = ret[1] = -1;
if (nums.length == 0)
return ret;
int left = 0, right = nums.length - 1, mid = 0;
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
if (nums[left] != target)
return ret;
else
ret[0] = left;
right = nums.length - 1;
while (left < right) {
mid = left + (right - left + 1) / 2;
if (nums[mid] <= target) {
left = mid;
} else {
right = mid - 1;
}
}
if (nums[left] != target)
return ret;
else
ret[1] = left;
return ret;
}
}总结二分模板
//查找区间左端点的模板：
while(left<right){
int mid=left+(right-left)/2;
if(...) left=mid+1;
else right=mid;
}
//查找区间右端点的模板：
while(left<right){
int mid=left+(right-left+1)/2;
if(...) left=mid;
else right=mid-1;
}
x 的平方根
69. x 的平方根 - 力扣（LeetCode）
解题思路：
mid*mid≤x时left=mid
mid*mid>x时right=mid-1
class Solution {
public int mySqrt(int x) {
long left = 0, right = x;
while (left < right) {
long mid = left + (right - left + 1) / 2;
if (mid * mid <= x)
left = mid;
else
right = mid - 1;
}
return (int) left;
}
}搜索插入位置
35. 搜索插入位置 - 力扣（LeetCode）
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1, mid = 0;
if (nums[left] > target)
return 0;
if (nums[right] < target)
return nums.length;
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}山脉数组的峰顶索引
852. 山脉数组的峰顶索引 - 力扣（LeetCode）
解法一：暴力枚举
解法二：二分查找算法（符合二段性，尽管不是有序数组）
arr[mid]>arr[mid-1]时，left=mid
arr[mid]<arr[mid-1]时，right=mid-1
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int left = 1, right = arr.length - 2;// 第一个元素和最后一个元素绝对不会是峰顶
int mid = 0;
while (left < right) {
mid = left + (right - left + 1) / 2;// 后面有-1，此处+1
if (arr[mid] > arr[mid - 1])
left = mid;
else if (arr[mid] < arr[mid - 1])
right = mid - 1;
else
break;
}
return left;//
}
}寻找峰值
162. 寻找峰值 - 力扣（LeetCode）
解法一：暴力解法（从第一个位置开始，一直向后走，分情况讨论）
解法二：二分查找
arr[mid]>arr[mid+1]时，right=mid
arr[mid]<arr[mid+1]时，left=mid+1
class Solution {
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1, mid = 0;
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid] < nums[mid + 1])
left = mid + 1;
else if (nums[mid] > nums[mid + 1])
right = mid;
else
break;
}
return left;//
}
}寻找旋转排序数组中的最小值
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
解法一：暴力查找最小值 O(n)
解法二：二分查找算法（二段性）
参考D点：A~B段：nums[i]>nums[n-1]；C~D段：nums[i]<=nums[n-1]；（D点下标为n-1）
A~B:nums[mid]>nums[n-1]时left=mid+1;
C~D:nums[mid]<=nums[n-1]时right=mid.
疑问：选择A点作为参照点是否可以？可以，但需要考虑边界情况
class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1, mid = 0;
int n = nums.length;
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid] > nums[n - 1])
left = mid + 1;
else
right = mid;
}
return nums[left];//
}
}0~n-1中缺失的数字
LCR 173. 点名 - 力扣（LeetCode）
解法一：哈希表
解法二：直接遍历找结果
解法三：位运算（异或：相同为零，相异为一）
解法四：高斯求和方式（数学方法）
以上解法时间复杂度均为O(n)
更优解法：二分
左区间：nums[mid]==mid时：left=mid+1;
右区间：nums[mid]! =mid时：right=mid.
细节：
[0，1，2，3]
0，1，2，3
class Solution {
public int takeAttendance(int[] records) {
int n = records.length;
int left = 0, right = n - 1, mid = 0;
if (records[n - 1] == n - 1)// 边界情况
return n;
while (left < right) {
mid = left + (right - left) / 2;
if (records[mid] == mid)
left = mid + 1;
else
right = mid;
}
return left;//
}
}