代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素_代码随想录算法训练营第一天|leetcode 704.二分查找、27移除元素

题目

704.二分查找

第一天，题目也没难度，当然也有易错点，比如区间的选取，要注意区间开闭

思路：

已知数组有序（升序），寻找目标值序号,而且也没有重复元素，buff拉满，直接上手写就可以

首先定义左右指针（概念上的），数组下标从0开始所以left=0，right=nums.size()-1;

接着进入循环，确定循环继续的条件，这里需要考率区间的选取

定义mid，这里看到视频说需要防止越界可以采用下列式子定义

int mid=(left+(left+right)）>> 2;

然后根据判断条件分三种情况进行讨论，移动指针即可；

附上ac代码：

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)/2;
        if(nums[mid]==target) return mid;
        else if(nums[mid]>target) right=mid-1;
        else if(nums[mid]<target) left=mid+1;
    }
    return -1;
    }
};

27.移除元素

看到题目第一想法就是暴力求解，利用两层for循环遍历，第一遍寻找数组中与目标值相等的元素，然后第二遍循环向前覆盖，数组长度减一

代码能力有点弱，没写出代码

看完讲解后，对于双指针法，一个字，秒！

双指针法理解：

设置两个指针（fast，slow）在同一个数组上移动，初值均为0，fast指针先移动，若fast指针所指向的值不是目标值，则将这个值赋值给slow指针所指向的位置，反之，若是要删除的元素，则快指针直接跳过，反应在slow指针上就是未更新元素，最后返回slow指针数值即可

附上ac代码：

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

之前几天都在考试，慢慢补卡吧