[学习笔记-C++篇]day19 二分法

现实打击max。

1.算法入门_二分法

1.1 二分查找1.2 *最长上升子序列(三)1.3 求最大平方根1.4 在旋转过的有序数组中寻找目标值1.5 在两个长度相等的排序数组中找到上中位数1.6 矩阵元素查找

题目：AB24 二分查找-I

牢记：
第一种：1）先判空；2）判断条件<=；3）求中间值用移位mid=left+right>>1代替mid=(left+right)/2；4）xm，令left=m+1;，x==m，返回m，5）找不到返回-1
第二种：1）先判空；2）判断条件<；3）同上，4）x<=m，令r=m，x>m，令l=m-1;，5）返回l，判断l是否等于目标值，等于返回该值，不等于返回-1。（left为找到的大于等于target的下标）

class Solution {
public:
    
    int search(vector& nums, int target) {
        // write code here
        int left=0;int right=nums.size()-1;
        while(left<=right)
        {
            int mid=left+right>>1;
            if(target>nums[mid]) left=mid+1;
            else if(target 
1.2 *最长上升子序列(三) 
最长上升子序列
 
class Solution {
public:
    
    vector LIS(vector& arr) {
        // write code here
        int n=arr.size();
        vector tail(n);//构建贪心序列，不是在找arr的最大增长子序列，因为这里是动态调整的，只是为了获取left索引
        vector curlen(n);//用于和arr对应，每一位表示同样索引下元素可以构成的最大递增子序列长度
        int ans=0;//ans是最大递增子序列的长度
        
        for(int i=0;i>1;
                if(tail[mid]>=arr[i]) right=mid;
                else left=mid+1;
            }
            tail[left]=arr[i];//找到增序序列中第1个大于等于arr[i]的元素，就替换他
            curlen[i]=left+1;//在left处进行替换，那么这之后的元素就不能算在该元素的最大递增序列，
                             //只能算这个位置及之前的，就是当前的tail的索引+1，即left+1
            if(left==ans) ans++;//我这样理解，ans是预设的一个right，因为一开始tail没有元素，
                                //不能right=-1，所以预设一个值，如果在此之前找到大于等于arr[i]的元素，
                                //就会在left处替换掉，不会影响到right预设值ans
                                //如果没找到，那么left=right，会在这个预设索引处新增元素，那么ans就要自增
        }
        
        vector res(ans);//ans肯定是比最长的递增序列最大索引还大1，也就是等于arr所有元素的最大递增序列最长的长度
        for(int i=arr.size()-1,j=ans;i>=0;i--)//在所有元素的最大递增序列长度向量curlen中找长度为ans的，
                                      //但要倒着找，这样可以找到字典序最小的
        {
            if(curlen[i]==j) res[--j]=arr[i];//这里要注意先做--j，这样才保证[]中是索引而不是长度
        }//这里一位一位的找，到这找的话，如果是递增序列长度相同的，也可以先确定较小的数字
        return res;
    }
};
 
1.3 求最大平方根 
题目：NC32 求平方根
 
class Solution {
public:
    
    int sqrt(int x) {
        // write code here
        int left=1;int right=x;
        while(left<=right)
        {
            int mid=left+right>>1;
            if(mid<=x/mid && (mid+1)>x/(mid+1)) return mid;
            else if(mid>x/mid) right=mid-1;
            else left=mid+1;
        }
        return 0;
    }
};
 
1.4 在旋转过的有序数组中寻找目标值 
在旋转过的有序数组中寻找目标值
 
法一：直接判断就行了
 
class Solution {
public:
    
    int search(vector& nums, int target) {
        // write code here
        for(int i=0;i 
法二：二分法
 
拷贝一个形象的区间划分图：
 
 和大佬的程序有点出入，主要是在区间判断的问题上，我的理解是可能在左区间（含边界），或者之外，也可能在右区间（含边界）或者之外，所以都用的是<=，在区间内判断的时候也是包含边界。
 
class Solution {
public:
    
    int search(vector& nums, int target) {
        // write code here
        int left=0,right=nums.size()-1;
        int mid;
        while(left<=right)
        {
            mid=left+right>>1;
            if(target==nums[mid]) return mid;
            if(nums[left]<=nums[mid])
            {
                if(targetnums[mid]) left=mid+1;
                else right=mid;
            }
            else if(nums[mid]<=nums[right])
            {
                if(targetnums[right]) right=mid-1;
                else left=mid;
            }
        }
        return -1;
    }
};
 
1.5 在两个长度相等的排序数组中找到上中位数 
在两个长度相等的排序数组中找到上中位数
 
class Solution {
public:
    
    int findMedianinTwoSortedAray(vector& arr1, vector& arr2) {
        // write code here
        int m=arr1.size();
        
        int c=0;
        int a=0,b=0;
        int ans;
        
        while(c 
只适用与2个长度相等数组。如果长度不相等，可能出现一个数组检索完的情况。
 
1.6 矩阵元素查找 
初步理解的时候，其实还是一个二分，但是是变形的二分，所以还是按照索引从左上到右下检索，然后一步步缩小区间，但是对于大矩阵还是会超时。
 
class Solution {
public:
    vector findElement(vector > mat, int n, int m, int x) {
        // write code here
        int left=0,right=m*n-1;//从左上角到右下角的索引
        int mid;//是总索引
        int i,j;//总索引对应的矩阵索引
        vector f;
        
        while(left<=right)
        {
            mid=left+right>>1;
            i=mid/m;
            j=mid%m;
            if(x==mat[i][j]) {f.push_back(i);f.push_back(j);return f;}
            if(x<=mat[i][j])//本来是x<=mid
                right=mid;
            else left=mid+1;
        }
        return f;
    }
};
 
有大佬使用了lower_bound () 函数用于在指定区域内查找不小于目标值的第一个元素函数。