Day1 704. 二分查找 27.移除元素
作业条：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY
704 二分查找
https://leetcode.cn/problems/binary-search/
文章讲解
https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
视频讲解
https://www.bilibili.com/video/BV1fA4y1o715
第一想法
二分查找经典题目，边界条件是left<=right，然后取中间的指针，和target比较，分别修改left和right的值直到最后找到；如果超出边界条件仍然没找到，返回-1；
看完解答后的想法：
需要注意循环不变量，也就是搜索的区间到底是左闭右闭还是左闭右开，并且要在设置边界值的时候坚持这个不变。
左闭右闭的写法，left = 0 ; right = num.size -1; while(left <= right ) left/right = mid+/-1;
左闭右开的写法，right = nums.size; while(left < right>) right = mid; left = mid+1;
二分查找需要思考的几个点：
- 循环的停止条件 while (low <= high)是因为有可能查找到两端的值
- 取中位数的方法 mid = low + (high-low)/2，防止high+low/2溢出
- 边界收缩：如果要找的值在左边这块，那么右边界-1；右边同理；-1是因为值不可能在mid；
- 返回值，找到返回mid，没找到即循环结束，返回-1；
- 其他输入异常情况
- 注意条件：是否是有序
实现过程中的问题
思路是对的，但是有细节需要改善；比如如何取中间值不越界；边界条件是<还是<=
27. 移除元素
题目链接：https://leetcode.cn/problems/remove-element/
文章讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP
第一想法：
暴力法：遍历判断当前元素是不是要移除的元素，如果是的话，把它后面所有元素前移；
双指针法：一个指针遍历数组，一个指针指向新数组当前位置；如果是要移除的元素，快指针+1，慢指针不变；如果不是要移除的元素，fast指向的值赋值给slow指向的值，fast+1，slow+1；返回slow
最终想法：
- 两个指针的初始位置都是0，快指针从0走到最后一位，慢指针只在快指针不等于val的时候才会走。
- 循环终止条件：快指针遍历完数组
- 返回值：慢指针-1+1（慢指针在的位置是最终数组+1的位置，所以-1，但是这个位置是下标，需要再+1）
实现过程中的问题：
第二次做，出错的地方在于应该是判断快指针的值和val，而不是慢指针
今日收获和学习时长
自己写的过了，复习了一遍，学习1.5h