LeetCode 二分章节 （持续更新中）
简单
35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为
O(log n)的算法。示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1示例 3:
输入: nums = [1,3,5,6], target = 7 输出: 4提示:
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums为 无重复元素 的 升序 排列数组-10^4 <= target <= 10^4
int searchInsert(vector<int>& nums, int target) {
if (nums[nums.size() - 1] < target)
return nums.size();
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid + 1;
else
right = mid;
}
return left;
}
69. x 的平方根
给你一个非负整数
x，计算并返回x的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
**注意：**不允许使用任何内置指数函数和算符，例如
pow(x, 0.5)或者x ** 0.5。示例 1：
输入：x = 4 输出：2示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。提示：
0 <= x <= 2^31 - 1
int mySqrt(int x) {
long long left = 0, right = x;
while (left < right) {
long long mid = left + (right - left + 1) / 2;
if (mid * mid > x)
right = mid - 1;
else
left = mid;
}
return (int)left;
}
704. 二分查找
给定一个
n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1提示：
- 你可以假设
nums中的所有元素是不重复的。n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止溢出
if (target > nums[mid])
left = mid + 1;
else if (target < nums[mid])
right = mid - 1;
else
return mid;
}
return -1;
}
LCR 173. 点名
某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组
records。假定仅有一位同学缺席，请返回他的学号。示例 1：
输入：records = [0,1,2,3,5] 输出：4示例 2：
输入：records = [0, 1, 2, 3, 4, 5, 6, 8] 输出：7提示：
1 <= records.length <= 10000
因为是升序数组，二分最优，如果不是升序数组268. 丢失的数字，可以用位运算，或高斯求和。
通过比对下标是否相等records[mid] != mid，来判断mid之前有没有同学缺席，再不断二分找到缺席同学的前一个。
int takeAttendance(vector<int>& records) {
int left = 0, right = records.size() - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (records[mid] != mid)
right = mid - 1;
else
left = mid;
}
// 特殊情况
if (records[0] == 1)
return 0;
return ++left;
}
中等
34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组
nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值
target，返回[-1, -1]。你必须设计并实现时间复杂度为
O(log n)的算法解决此问题。示例 1：
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]示例 2：
输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]示例 3：
输入：nums = [], target = 0 输出：[-1,-1]提示：
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9nums是一个非递减数组-10^9 <= target <= 10^9
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.size() == 0)
return {-1, -1};
int ans_left = -1, ans_right = -1;
// 左端点
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid + 1;
else
right = mid;
}
if (nums[left] != target)
return {-1, -1};
ans_left = left;
// 右端点
left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (nums[mid] <= target)
left = mid;
else
right = mid - 1;
}
ans_right = right;
return {ans_left, ans_right};
}
利用库函数。
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.size() < 1)
return {-1, -1};
int left = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
int right = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;
if (left >= nums.size() || nums[left] != target)
left = right = -1;
return {left, right};
}
153. 寻找旋转排序数组中的最小值
已知一个长度为
n的数组，预先按照升序排列，经由1到n次 旋转 后，得到输入数组。例如，原数组nums = [0,1,2,4,5,6,7]在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,2]- 若旋转
7次，则可以得到[0,1,2,4,5,6,7]注意，数组
[a[0], a[1], a[2], ..., a[n-1]]旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。给你一个元素值 互不相同 的数组
nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须设计一个时间复杂度为
O(log n)的算法解决此问题。示例 1：
输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。示例 2：
输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。示例 3：
输入：nums = [11,13,15,17] 输出：11 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的所有整数 互不相同nums原来是一个升序排序的数组，并进行了1至n次旋转
通过nums[mid] < nums[n - 1]，来判断是否是翻转后的在数组最后一个元素下面的区间，进行不断二分。
int findMin(vector<int>& nums) {
int n = nums.size();
int left = 0, right = n - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[n - 1])
right = mid;
else
left = mid + 1;
}
return nums[left];
}
162. 寻找峰值
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组
nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设
nums[-1] = nums[n] = -∞。你必须实现时间复杂度为
O(log n)的算法来解决此问题。示例 1：
输入：nums = [1,2,3,1] 输出：2 解释：3 是峰值元素，你的函数应该返回其索引 2。示例 2：
输入：nums = [1,2,1,3,5,6,4] 输出：1 或 5 解释：你的函数可以返回索引 1，其峰值元素为 2； 或者返回索引 5， 其峰值元素为 6。提示：
1 <= nums.length <= 1000-231 <= nums[i] <= 231 - 1- 对于所有有效的
i都有nums[i] != nums[i + 1]
这题和这道题852. 山脉数组的峰顶索引基本相同。
int findPeakElement(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (nums[mid] > nums[mid - 1])
left = mid;
else
right = mid - 1;
}
return left;
}
611. 有效三角形的个数
给定一个包含非负整数的数组
nums，返回其中可以组成三角形三条边的三元组个数。示例 1:
输入: nums = [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3示例 2:
输入: nums = [4,2,3,4] 输出: 4提示:
1 <= nums.length <= 10000 <= nums[i] <= 1000
两层for循环枚举最小的两个数，再通过二分查找确定满足三角形条件的边界值。但这题的最优解是双指针。
int triangleNumber(vector<int>& nums) {
if (nums.size() < 2)
return 0;
sort(nums.begin(), nums.end());
int ans = 0;
for (int i = 0; i < nums.size() - 2; ++i) {
// 跳过为零的数
if (nums[i] == 0)
continue;
for (int j = i + 1; j < nums.size() - 1; ++j) {
int sum = nums[i] + nums[j];
// 找到小于两数之和，最右边的边界值
int p = lower_bound(nums.begin(), nums.end(), sum) - nums.begin() - 1;
// (j + 1, p)都是可以构成三角形的值
ans += p - j;
}
}
return ans;
}
852. 山脉数组的峰顶索引
给定一个长度为
n的整数 山脉 数组arr，其中的值递增到一个 峰值元素 然后递减。返回峰值元素的下标。
你必须设计并实现时间复杂度为
O(log(n))的解决方案。示例 1：
输入：arr = [0,1,0] 输出：1示例 2：
输入：arr = [0,2,1,0] 输出：1示例 3：
输入：arr = [0,10,5,2] 输出：1提示：
3 <= arr.length <= 10^50 <= arr[i] <= 10^6- 题目数据 保证
arr是一个山脉数组
关键就是通过arr[mid] > arr[mid - 1]，来判断mid处是否是递增的来不断二分。
int peakIndexInMountainArray(vector<int>& arr) {
int left = 0, right = arr.size() - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (arr[mid] > arr[mid - 1])
left = mid;
else
right = mid - 1;
}
return left;
}