1. 二分查找
704. 二分查找
https://leetcode.cn/problems/binary-search/
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。
你必须编写一个具有 O(log n) 时间复杂度的算法。
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0,right=nums.size()-1;
while(left<=right)
{
int order=left+(right-left)/2;
if(target>nums[order])
left=order+1;
else if(target<nums[order])
right=order-1;
else
return order;
}
return -1;
}
};
最基础的写法，但有时会因为特殊情况，导致效率约等于暴力算法。
2. x的平方根
69. x 的平方根 https://leetcode.cn/problems/sqrtx/
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
class Solution {
public:
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)
left=mid;
else
right=mid-1;
}
return left;
}
};
优化写法，查找0~X区间，返回左端。
3. 搜索插入位置
LCR 068. 搜索插入位置https://leetcode.cn/problems/N6YdxV/
给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int 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;//出现减号，上面mid中+1
}
if(nums[left]<target)
return left+1;
else
return left;
}
};
注意：写法格式
4. 山脉数组的峰顶索引
LCR 069. 山脉数组的峰顶索引https://leetcode.cn/problems/B1IidL/
符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：
- arr.length >= 3
- 存在 i（0 < i < arr.length – 1）使得：
- arr[0] < arr[1] < … arr[i-1] < arr[i]
- arr[i] > arr[i+1] > … > arr[arr.length – 1]
给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i – 1] < arr[i] > arr[i + 1] > … > arr[arr.length – 1] 的下标 i ，即山峰顶部。
class Solution {
public:
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;
}
};
5. 丢失的数字
268. 丢失的数字https://leetcode.cn/problems/missing-number/
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数
class Solution {
public:
int missingNumber(vector<int>& nums)
{
sort(nums.begin(),nums.end());
int left=0,right=nums.size()-1;
while(left<right)
{
int mid=left+(right-left+1)/2;
if(nums[mid]==mid)
left=mid;
else
right=mid-1;
}
if(nums[0]!=0)
return 0;
return left+1;
}
};
异或法：
class Solution {
public:
int missingNumber(vector<int>& nums)
{
int sum=0;
for(auto e:nums)sum^=e;
for(int i=0;i<=nums.size();i++)sum^=i;
return sum;
}
};
⭐6. 在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。
请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size()==0)
return {-1,-1};
int left=0,right=nums.size()-1;
vector<int> result;
//二分左端点;
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};
else result.push_back(left);
//二分右端点
right=nums.size()-1;
while(left<right)
{
int mid=left+(right-left+1)/2;
if(nums[mid]<=target)
left=mid;
else
right=mid-1;
}
result.push_back(right);
return result;
}
};
注意：查找左端和右端的写法细节。
库函数方法：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int start = ranges::lower_bound(nums, target) – nums.begin();
if (start == nums.size() || nums[start] != target) {
return {-1, -1};
}
int end = ranges::upper_bound(nums, target) – nums.begin() – 1;
return {start, end};
}
};
7. 寻找旋转 排序数组中的最小值
153. 寻找旋转排序数组中的最小值https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/
已知一个长度为 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) 的算法解决此问题
class Solution {
public:
int findMin(vector<int>& arr) {
int left=0,right=arr.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(arr[mid]>arr[right])
left=mid+1;
else
right=mid;
}
return arr[left];
}
};
注意：逻辑很重要。
8. 搜索二维矩阵
74. 搜索二维矩阵https://leetcode.cn/problems/search-a-2d-matrix/
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int left=0,right=matrix[0].size()-1,floor=0;
while(left<right&&floor<matrix.size())
{
while(floor<matrix.size()&&target>matrix[floor][right])
floor++;
if(floor==matrix.size())
return false;
int mid=left+(right-left+1)/2;
if(matrix[floor][mid]<=target)
left=mid;
else
right=mid-1;
}
while(floor<matrix.size()&&target>matrix[floor][right])
floor++;
if(floor==matrix.size())
return false;
if(matrix[floor][left]==target)
return true;
else
return false;
}
};
