二分搜索
紧接下来就是二分查找了，二分或者说分治的思路很简单也很常用，比如归并、快排等算法都用到了分治的思想。这种思想比较熟悉了，直接来做题吧
35. 搜索插入位置
给定排序过后的数组和一个目标值，要找到这个值的位置或者应该插入的位置。可以用数组来做，或者用双指针在 lc 里更加常见（？
给出左右指针分别指在数组的前后，算中点，然后比较中点值和目标值的大小，然后修改左右指针的位置为中点的左/右侧即可。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left=0;
int right=nums.size()-1;
while(left<=right){
int mid=(left+right)/2;
if(nums[mid]==target) return mid;
if(nums[mid]<target){
left=mid+1;
}
if(nums[mid]>target) {
right=mid-1;
}
}
return left;
}
};74. 搜索二维矩阵
题目给出了一个按照增序排列的二维矩阵表格，并且严格保证下一行的第一个元素＞上一行的最后一个元素，要求寻找给定值在矩阵中是否存在，所以我们可以有几个自然的思路：
- 将二维数组拉平，然后用普通二分进行查找
- 将给定值与每行的第一列/最后一列的值比较来确定应该在第几行继续查找，然后再使用二分在行内进行查找
我们分别来实现，首先第一种：
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
vector<int> nums;
for(int i=0;i<matrix.size();i++){
nums.insert(nums.end(),matrix[i].begin(),matrix[i].end());
}
int left=0;
int right=nums.size()-1;
while(right>=left){
int mid=left+(right-left)/2;
if(nums[mid]==target) return true;
if(target > nums[mid]) {
left=mid+1;
}
if(target<nums[mid]){
right=mid-1;
}
}
return false;
}
};哦豁，发现被 ban 了，所以把所有数组真的摊平是不行的，那怎么办呢？可以通过计算来实现模拟将数组摊平
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m=matrix.size();
int n=matrix[0].size();
int left=0;
int right=m*n-1;
while(right>=left){
int mid=left+(right-left)/2;
int row=mid/n;
int col=mid%n;
if(matrix[row][col]==target) return true;
if(target > matrix[row][col]) {
left=mid+1;
}
if(target<matrix[row][col]){
right=mid-1;
}
}
return false;
}
};OK，我们接着来实现我们的第二种想法，要注意的是，我们两次查找都要用二分查找
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
int n = matrix[0].size();
int top = 0;
int bottom = m-1;
int row = -1;
while(bottom >= top){
int mid = top+(bottom-top)/2;
if(target < matrix[mid][0]){
bottom = mid-1;
}
else if(target > matrix[mid][n-1]){
top = mid+1;
}
else{
row = mid;
break;
}
}
if (row == -1) {
return false;
}
int left = 0;
int right = n-1;
while(right >= left){
int mid = left+(right-left)/2;
if(target < matrix[row][mid]){
right = mid-1;
}
if(target > matrix[row][mid]){
left = mid+1;
}
if(target == matrix[row][mid]){
return true;
}
}
return false;
}
};34. 在排序数组中查找元素的第一个和最后一个位置
本题给出一个递增排序的列表，要求给出目标值在列表中的头尾位置
头位置很自然，直接用二分来找即可；那尾呢，我一开始的想法是二分找到一个后一点一点移动另外一个指针直到找到另外一个点，不过这种方法并不能满足题目要求的时间复杂度，经过妙妙提示后发现我们并不需要找目标值的尾位置，我们只用找目标值的下一个值的头位置即可，然后在用这个位置-1 就得到了目标值的尾位置
class Solution {
public:
int lowerBound(vector<int>&nums,int target){
int left=0;
int right=nums.size()-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]>=target){
right=mid-1;
}else{
left=mid+1;
}
}
return left;
}
vector<int> searchRange(vector<int>& nums, int target) {
int start=lowerBound(nums,target);
if(start==nums.size() || nums[start]!=target){
return {-1,-1};
}
int end=lowerBound(nums,target+1)-1;
return {start,end};
}
};33. 搜索旋转排序数组
依旧是 lc 的经典非人类语言叙述，可以理解为把一个升序序列的一点设为 k 点，把 k 点前后的两个子序列交换顺序，但是这个题干其实不重要。
重要的是要理解，在进行二分后，一定有一半是已经排序好的，另一半是没排序好的，再进行二分就会再有一半排序好的，一直分到两侧只有一个元素，他们自身就是排序好的（也就是归并的分治思想
所以按照这个思路写下去就行了
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0;
int right=nums.size()-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]==target){
return mid;
}
if(nums[left]<=nums[mid]){
if(target>=nums[left] && target<nums[mid]){
right=mid-1;
}else{
left=mid+1;
}
}
if(nums[right]>nums[mid]){
if(target>=nums[mid] && target<=nums[right]){
left=mid+1;
}else{
right=mid-1;
}
}
}
return -1;
}
};153. 寻找旋转排序数组中的最小值
本题仍然需要理解它所谓的旋转其实就是一分为二，后面的搬到前面与任何一次二分的结果的一边都是已经排序好的结果。
需要注意的是，这里我们应当使用右侧来比较区间是否为已排序好的，因为在多次旋转之后，只有最右侧的元素是没有被旋转影响的，才能真实的反应出序列的左/右侧是否已经排序好，最后返回 left 就行了
class Solution {
public:
int findMin(vector<int>& nums) {
int left=0;
int right=nums.size()-1;
while(left<right){
int mid=left+(right-left)/2;
if(nums[mid]<=nums[right]){
right=mid;
}else{
left=mid+1;
}
}
return nums[left];
}
};4. 寻找两个正序数组的中位数
有点何意味的题，确实不是很好理解，做这个题首先要理解什么叫中位数，以及什么叫两个数组的中位数。
中位数：可以将数集划分为数量相等的上下两部分的数，一个数集中最多有一半的数小于中位数，最多有一半的数大于中位数，否则必有若干值等同于中位数。
叽里咕噜说什么呢，这和我平时理解的中位数也没区别啊，但是在下面写代码的时候那可太有用了（
两个数组的中位数其实就是两个数组合并后的新数集的中位数，那么最笨的解法就来了，先合并再取中，但是这很明显不满足题目要求的O(log(m+n))时间复杂度
那怎么优化呢？我们可以先找到合并后的数组的中位数应该在的位置，然后去找到这第 k 个数，那怎么去找呢，说真的这想法有点神秘了（）
先找 M 和 N 两个数组的 k/2 位置然后比较，其中小的那一段里面肯定没有第 k 小的数；于是便排除了 k/2 个数，然后让k=k-k/2
……不想解释这段玩意了，看不懂的时候就在就给哈基米让它讲一遍吧
class Solution {
public:
int getK(const vector<int>& nums1,int start1,const vector<int>& nums2,int start2,int k){
int m=nums1.size();
int n=nums2.size();
while(true){
if(start1==m){
return nums2[start2 + k - 1];
}
if(start2==n){
return nums1[start1 + k - 1];
}
if(k==1){
return min(nums1[start1],nums2[start2]);
}
int newStart1 =min(start1+k/2-1,m-1);
int newStart2 =min(start2+k/2-1,n-1);
int pivot1=nums1[newStart1];
int pivot2=nums2[newStart2];
if(pivot1<=pivot2){
k-=(newStart1-start1+1);
start1=newStart1+1;
}else{
k-=(newStart2-start2+1);
start2=newStart2+1;
}
}
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int total=nums1.size()+nums2.size();
if(total%2==1){
return getK(nums1,0,nums2,0,(total+1)/2);
}else{
return((getK(nums1,0,nums2,0,total/2)+getK(nums1,0,nums2,0,total/2+1))/2.0);
}
}
};喂喂喂，这太抽象了，有没有人类一点的做法？有的有的，划分数组法的思维就更贴近一点人类了，它的时间复杂度甚至能低到O(log(min(m,n)))
前面说了一个数集中最多有一半个数大于中位数、最多有一半个数小于中位数，所以我们在两个数组中分别切一刀让左边的长度之和为数集的一半就行；并且，为了保持数组的先序，还需要保证左边的所有数小于右边的所有数，而原数组本身就是先序的保证了L1<R1,L2<R2，我们只需在额外保证L1<R2,L2<R1即可
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if(nums1.size()>nums2.size()){
return findMedianSortedArrays(nums2,nums1);
}
int m=nums1.size();
int n=nums2.size();
int totalL=(m+n+1)/2;
int left=0;
int right=m;
while(left<=right){
int i=left+(right-left)/2;
int j=totalL-i;
int L1=(i==0)?INT_MIN : nums1[i-1];
int R1=(i==m)?INT_MAX : nums1[i];
int L2=(j==0)?INT_MIN : nums2[j-1];
int R2=(j==n)?INT_MAX : nums2[j];
if(L1<=R2 && L2<=R1){
if((m+n)%2==1){
return max(L1,L2);
}else{
return (max(L1,L2)+min(R1,R2))/2.0;
}
}else if(L1>R2){
right=i-1;
}else{
left=i+1;
}
}
return 0.0;
}
};
0 评论