代码随想录算法训练营day01|704. 二分查找，27. 移除元素，977.有序数组的平方

704. 二分查找

题目链接：https://leetcode.cn/problems/binary-search/description/

本人代码：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low=0,high=nums.size()-1;//此处分情况讨论
        return searchTarget(nums,low,high,target);
    }
    int searchTarget(vector<int>& nums,int low,int high,int target){
        while(high>=low){//此处分情况讨论
        int mid=(low+high)/2;//可作差除以二后加较小数防止溢出
        if(nums[mid]==target) {return mid;}
        if(nums[mid]>target) {high=mid-1;}//此处分情况讨论
        if(nums[mid]<target) {low=mid+1;}//此处分情况讨论
        }
        return -1;
    }
};

本题左闭右闭区间，另有左闭右开等情况，分情况讨论。

27. 移除元素

题目链接：https://leetcode.cn/problems/remove-element/description/

本人代码（暴力解法）：

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

将不含val的数组元素依次向前移动形成新数组

双指针解法（快慢指针）：

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];
            }
        }
        return slow;
    }
};

快指针：依次向后寻找不含val的新数组元素
慢指针：记录新数组的下标

977.有序数组的平方

题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/

本人代码（暴力解法）：

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

先平方再冒泡排序

双指针解法（左右指针）：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> result(nums.size(),0);
        int i=0;
        int j=nums.size()-1;
        int k=nums.size()-1;
        while(i<=j){
            if(nums[i]*nums[i]>=nums[j]*nums[j]){
            result[k--]=nums[i]*nums[i];
            i++;
            }
            else{
            result[k--]=nums[j]*nums[j];
            j--;
            }
        }
        return result;
    }
};

左右指针都向中间移动，较大的放入数组末端直到两指针相遇