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

704.二分查找（文章链接、视频链接）

1.本人背景是非科班跨考，基础较差，只会一点点C，看到题目的第一反应是想到的循环居然是for循环……。这是不正确的，反思了一下for循环更适用于从头到尾的循环遍历，而while循环适用于条件循环遍历、范围更广。

2.二分法思想的核心在于循环条件以及边界情况的处理，处理的关键在于对区间概念的正确理解。什么是区间？由高中知识易知像[1,2]这样表示的是一个从1到2左右封闭的区间，1和2都能取到，而[1,2）这样的表示的是一个从1到2的左闭右开的区间可以取到1不能取到2。针对于该题数组的指针区间[left，right]应理解为能取到数组nums[left]一直到数组nums[right] 之间的所有元素，[left,right)应理解为能取到数组下标为left一直到下标为right-1的所有元素。

下面给出左闭右闭区间代码

int search(int* nums, int numsSize, int target){
    int left=0;
    int right=numsSize-1;
    while(left<=right){//循环区间能取到左右相等
        int mid=(left+right)/2;
        if(nums[mid]<target)
            left=mid+1;//表示mid已经不在查找区间了
        else if(nums[mid]>target)
            right=mid-1;
        else
            return mid;
    }
    return -1;
}

? ?下面给出左闭右开区间算法

int search(int* nums, int numsSize, int target){
    int left=0;
    int right=numsSize;//右下标为开区间，为保证取到大小为numsSize的数组的所有元素
    while(left<right){//此时左右下标不能相等，相等时不是查找区间
        int mid=(left+right)/2;
        if(nums[mid]<target)
            left=mid+1;
        else if(nums[mid]>target)
            right=mid;//若等于mid-1，则nums[mid-1]这个元素就不在查找区间了
        else
            return mid;
    }
    return -1;
}

27.移除元素（文章链接、视频链接）

1.第一反应是两重循环暴力解法，但在外循环i的值上出现了卡壳，下面给出暴力解算法代码

int removeElement(int* nums, int numsSize, int val) {
    int i,j;
    for(i=0;i<numsSize;i++){
        if(nums[i]==val){
            for(j=i;j<numsSize-1;j++){//发现目标元素就前移覆盖
                nums[j]=nums[j+1];
            }
            numsSize--;//numSize与i的值要在if条件成立的情况下才发生变化
            i--;//元素前移后i的值也发生变化
        }
    }
    return numsSize;
}

2.巧思快慢指针法（思想类似于前面的快指针探路，后面的慢指针保留需要的元素）

int removeElement(int* nums, int numsSize, int val) {
    int quick,slow=0;
    for(quick=0;quick<numsSize;quick++){
        if(nums[quick]!=val)
        nums[slow++]=nums[quick];
    }
    return slow;
}

总结：实际上手就会出现各种问题，鉴于C语言刷题效率较低，我打算在刷题的同时进行C++的学习，希望能跟上大家的节奏。此外，本人水平较低，如有错误不当之处，烦请批评指正。