二分法-算法总结

 数组常用算法：二分查找，双指针，滑动窗口，模拟行为，我们将从这四个思想介绍

---

 

目录

二分查找

移除元素

长度最小的子数组

螺旋矩阵

---

二分查找

使用条件：

1.有序数组，2.无重复元素

原理：

在数组中先从中间位置的元素开始判断和目标值的关系，然后调整left或者right，从而实现不用按个遍历整个数组。

方法：

对于在一个有序数组中寻找目标元素的位置类问题，采用二分法。常见二分法的写法分为两种

1.左闭右闭

2.左闭右开

我们将附上两者代码。

现在说一下具体的实现方法：我们以左闭右闭举例。

1.确定left和right的值，由于都是闭合，则表示左右区间元素都可以取到

int left=0,right=nums.size()-1;

 2.确定while的判断条件，由于都是闭合，则表示区间元素都可以取到

while(left<=right){
 
}

3.确定left和right的变换情况，由于都是闭合，则表示区间元素都可以取到，那么下一次判断则不需要边界元素

if(nums[middle]>target){
    right=middle-1;
}
else if(nums[middle]
    left=middle+1;
}
else{
    //找到了
}

综上所述，整个代码就分析完了，同理，左闭右开也是如此，两个代码如下：

1.左闭右闭

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
       
        while(left<=right){
             int middle=left+((right-left)>>1);
            if(nums[middle]>target){
                right=middle-1;
            }
            else if(nums[middle]
                left=middle+1;
            }
            else{
                return middle;
            }
        }
        return -1;
    }
};

2.左闭右开

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0,right=nums.size();
       
        while(left
             int middle=left+((right-left)>>1);
            if(nums[middle]>target){
                right=middle;
            }
            else if(nums[middle]
                left=middle+1;
            }
            else{
                return middle;
            }
        }
        return -1;
    }
};

常见题型：

704. 二分查找 - 力扣（LeetCode）https://leetcode.cn/problems/binary-search/367. 有效的完全平方数 - 力扣（LeetCode）https://leetcode.cn/problems/valid-perfect-square/35. 搜索插入位置 - 力扣（LeetCode）https://leetcode.cn/problems/search-insert-position/34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

移除元素

使用条件：

1.不产生新的内存空间，2.原地删除指定元素

原理：

数组中无法直接删除元素，都是通过覆盖实现，因此思路就是遍历原数组，利用其他值把特定值进行覆盖，当遍历完成后即完成了新数组。需要注意的是，数组在内存中还是之前大小，只是按照你的想法留下了一些元素。

方法：

对于删除特定元素的问题，一般有两个办法，1暴力法，2双指针法。

我们将附上两者代码。

现在说一下具体的实现方法：我们以暴力法举例。

1.遍历整个数组

for(int i=0;isize();i++){
    
}

2.当遍历数组发现目标元素时，把目标元素后所有元素进行前移

if(nums[i] == val){
    for(int j = i +1 ; j < nums.size(); j++){
        nums[j-1] = nums[j];
    }
    //数组大小--
}

综上所述，整个代码就分析完了，代码如下：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for(int i = 0; i
            if(nums[i]==val){
                for(int j = i + 1; j
                    nums[j-1]=nums[j];
                }
                i--;
                size--;
            }
        }
        return size;
    }
};

我们以双指针法举例。

双指针的思路是：快指针遍历整个数组，慢指针为需要保留元素的下标。当快指针符合条件时（一般是≠），慢指针++，然后把当前快指针的值赋值给慢指针下标，然后++

1.定义一个快指针来遍历所有元素，一个慢指针保留有效元素的下标

int slow=0;
        for(int fast = 0; fast < nums.size(); fast++){
            
 
            }
        }

2.当快指针遍历的元素满足条件时，把保留元素存入数组，且下标为当前慢指针，当满足一次后，慢指针后移，因此，整体代码如下

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow=0;
        for(int fast = 0; fast < nums.size(); fast++){
            if(nums[fast] != val){
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
};

常见题型：

27. 移除元素 - 力扣（LeetCode）https://leetcode.cn/problems/remove-element/submissions/

26. 删除有序数组中的重复项 - 力扣（LeetCode）https://leetcode.cn/problems/remove-duplicates-from-sorted-array/submissions/ 283. 移动零 - 力扣（LeetCode）https://leetcode.cn/problems/move-zeroes/

977. 有序数组的平方 - 力扣（LeetCode）https://leetcode.cn/problems/squares-of-a-sorted-array/

长度最小的子数组

使用条件：

寻找数组中的子数组

原理：

利用双指针思想，有两个指针分别指向数组。但是：滑动窗口中，我们用last进行移动数组，first只有在满足条件的时候才进行移动。

因此，我们定义last在一个for中不断遍历数组，且每次遍历时把当前last位置的元素++。然后判断该元素和是否满足条件。当满足条件后，我们先求当前的字符串长度，然后开始first++，然后元素和减去first之前的元素，再判断元素和是否满足。

方法：

1.定义first指向0位置，last指向0位置，ans=INT_MAX，元素和sum=0

        int first = 0;
        int ans =INT_MAX;
        int sum = 0;

2.移动last指针，遍历整个数组，并求每次移动后的元素和

        for(int last = 0; last < nums.size(); last++){
            sum += nums[last];
            }

 3.对元素和进行判断是否满足要求，如果满足，先求得当前字符串长度，然后把first++，然后把之前的first的值移除，再判断元素和。因此总代码如下：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int first = 0;
        int ans =INT_MAX;
        int sum = 0;
        for(int last = 0; last < nums.size(); last++){
            sum += nums[last];
            while(sum >= target){
                ans = min(ans , last - first + 1);
                sum -= nums[first++];
            }
        }
        return ans == INT_MAX ? 0 : ans;//防止空数组
    }
};

 如下：为暴力法

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
    int ans=INT_MAX;
    for(int i = 0; i < nums.size(); i++){
        int sum = 0;
        for(int j = i; j < nums.size(); j++){
            sum += nums[j];
            if(sum >= target){
                ans=min(ans, j - i + 1);
            }
        }
    }
    return ans == INT_MAX ? 0 : ans;
    }
};

常见题型：

209. 长度最小的子数组 - 力扣（LeetCode）https://leetcode.cn/problems/minimum-size-subarray-sum/

螺旋矩阵

方法：

采取左闭右开

1.定义其实位置startx=starty=0，offest=1控制边界长度，i，j控制移动,loop控制圈数，mid控制中间那个格子

        int startx = 0, starty = 0;
        int offest = 1;
        int i, j;
        int loop = n / 2;//转的圈数
        int mid = n / 2 ;//中间补充的位置
        int count = 1;

2.上排，采用左闭右开，数据采用（i，j），因此上排遍历只有 j 改变，i 不动

for( j = starty; j < n - offest; j++){
           ans[startx][j] = count++;
            }

2.右排，采用左闭右开，数据采用（i，j），因此右排遍历只有i 改变，j 不动

            for( i =startx; i < n -offest; i++){
                ans[i][j] = count++;
            }

同理可以得到另外两排数据，总代码如下：

class Solution {
public:
    vectorint>> generateMatrix(int n) {
        vectorint>>ans(n,vector<int>(n,0));
        int startx = 0, starty = 0;
        int offest = 1;
        int i, j;
        int loop = n / 2;//转的圈数
        int mid = n / 2 ;//中间补充的位置
        int count = 1;
        while(loop--){
            i = startx;
            j = starty;
            //上
            for( j = starty; j < n - offest; j++){
                ans[startx][j] = count++;
            }
            //右
            for( i =startx; i < n -offest; i++){
                ans[i][j] = count++;
            }
            //下
            for(; j > starty; j--){
                ans[i][j] = count++;
            }
            //左
            for(; i > startx; i--){
                ans[i][j] = count++;
            }
            //第二圈
            startx++;
            starty++;
            offest+=1;
            }
            if(n % 2){
                //奇数
                ans[mid][mid] = count;
           
        }
         return ans;
    }
};

相关题目：

59. 螺旋矩阵 II - 力扣（LeetCode）https://leetcode.cn/problems/spiral-matrix-ii/