1、二分查找
很经典的一道题，直接用二分模板即可，但有几点需要注意：
- 不是传统的二分模板，l 和 r 是永远不会交错的，只会到分界线处相邻，即 r - l == 1
- 心中要清楚，l 分区和 r 分区在题目中分别代表的性质
- 循环结束后，如果需要使用 l、r 判断某条件时，要考虑到可能分区根本没有移动的情况，此时 l / r 是在数组合法范围外的！
二分模板：
详细说明，往期博客：二分专题----如何优雅的写出二分
l=-1, r=N //在(l,r)的数组索引开区间内，数组元素都是灰色的while l+1≠r //l+1=r时，蓝红区域接触m = ⌊(l+r)/2⌋ //开区间中间元素if IsBlue(m)l=m //蓝色区域向右拓展到中间元素elser=m //红色区域向左拓展到中间元素//根据实际情况返回l或r，但要注意：返回谁就要对谁做越界判断！
return l or r 本题代码：
class Solution {
public:int search(vector<int>& nums, int target) {int n = nums.size();int l = -1, r = n;while(r - l > 1) // l + 1 != r{int mid = (l + r) >> 1;if(nums[mid] < target)l = mid;elser = mid;}int ret = -1;if(r <n && nums[r] == target) // 先判断r是否合法ret = r;return ret;}
};2、移除元素
本题类似于实现vector中的erase方法，只不过标准库的erase是只能用迭代器删除元素的：
而本题要实现的是，指定vector中的一个值val，将数组中所有val值都删除，并且返回删除后的有效元素个数，且可以打乱原有的顺序。
本题的数据范围很小，最多只有100个元素，很直接的我们可以想到暴力做法：
1、双重循环：外层找出val，内层移动后续元素覆盖时间复杂度是O(n),空间复杂度也是O(1)。
2、空间换时间：新开一个vector，遍历原vector，将不是val的值插入新的vector中，再赋值给原vector，这样时间复杂度是O(n),空间复杂度也是O(n)。
第二种方法并不符合题意，题目要求原地修改数组 ，那么除了第一种暴力，还有更优化的做法吗？-------双指针，数组操作中很常见的优化方法
1、同向双指针：定义快慢指针，slow在原数组中更新新数组，fast遍历数组元素，将不是val的元素更新到slow
2、对撞指针：定义左右指针，左指针找出等于val的位置，右指针找出不等于val的指针，然后将右指针指向的值赋值给左指针处，直到左右指针错过。
对撞指针中有很多细节，循环中取等问题、赋值时的条件判断
代码如下：
暴力代码1：双重循环：
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
class Solution {
public:int removeElement(vector<int>& nums, int val) {int size = nums.size();for (int i = 0; i < size; i++) {if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位for (int j = i + 1; j < size; j++) {nums[j - 1] = nums[j];}i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位size--; // 此时数组的大小-1}}return size;}
};暴力代码2：空间换时间（不满足原地修改数组的题意！）
class Solution {
public:int removeElement(vector<int>& nums, int val) {int n = nums.size();vector<int> arr;for(int i = 0; i < n; i++){if(nums[i] != val)arr.push_back(nums[i]);}nums = arr;return arr.size();}
};双指针代码1：同向双指针
class Solution {
public:int removeElement(vector<int>& nums, int val) {int n = nums.size();int fast, slow = 0;//fast遍历所有元素，忽略val，其余赋值到slow处//slow指向待更新的新数组处，slow之前的全部是合法元素for(fast = 0; fast < n; fast++){if(nums[fast] != val){nums[slow++] = nums[fast];}}return slow;}
};双指针代码2：对撞指针
class Solution {
public:int removeElement(vector<int>& nums, int val) {int n = nums.size();int l = 0, r = n - 1;//必须取等，如果不取等，l、r相遇的位置还没有判断//如果是合法值，不取等的话，l不会右移，最终结果会遗漏while(l <= r){// l找出等于val的值while(l <= r && nums[l] != val) l++;// r找出不等于val的值while(l <= r && nums[r] == val) r--;//上面的寻找中，l、r可能已经错过了，需要判断if(l < r) nums[l++] = nums[r--];}//l代表：l之前的全是合法元素（全都是经过l判断过的）return l;}
};
