704 二分查找
力扣题目连接：https://leetcode.cn/problems/binary-search/
代码随想录讲解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
题目
分析
二分查找有左闭右闭[left, right]和左闭右开[left, right)两种方式。
left、right 为索引
对于左闭右闭方式
输入 nums = [-1,0,3,5,9,12] , target = 5
左闭右闭的意思时左指针索引和右指针索引都在有效索引上，如图初始化
left指针和right指针
初始化之后，要利用二分查找法来找到对应的target目标数字，二分查找顾名思义就是一分为二，所以使用mid指针来表示，mid = (right-left)/2+left 这个就是找到left指针和right指针所对应的二分后的中间位置。
mid = (right-left)/2+left这样计算是为了避免数值溢出
如果使用mid = (right+left)/2的话，right+left的值在int类型下可能存不下导致溢出
此时找到了左右指针的中间位置即mid所指。现在需要判断nums[mid]的值与target值的大小，从而确定是left指针移动还是right指针移动。
nums[mid]是等于3的，是小于target的值5，所以索引小于等于mid对应的数值肯定都是小于target的，肯定不存在5这个目标数，所以left指针要移动到mid+1的位置
此时left指针和right指针又是新一轮的新值。重复上述操作，再次找到mid的值，即mid = (right-left)/2+left 即 mid等于4
再次判断nums[mid]与target的大小，显然nums[mid]的值为9，target的目标值为5，即nums[mid]大于target，由于数组里的存数都是从小到大排序的，所以索引大于等于mid对应的数组值都是比target目标值5大的，所以需要将right指针移动到mid-1位置
left指针和right指针都调整好了之后，又重复上述操作计算mid值，即mid的值为3
此时将nums[mid]与target进行比较，发现nums[mid]等于target，即找到了目标值的索引，所以直接return mid就行。如果找不到肯定会出现left>right的情况，则直接退出循环，返回-1即可。
代码如下：
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size()-1;
int mid = 0;
while(left <= right) {
mid = (right - left) / 2 + left; // 计算mid
if(nums[mid] < target) { // 将mid所指的数值与target进行比较
left = mid + 1; // 调整left
}else if (nums[mid] > target) { // 将mid所指的数值与target进行比较
right = mid - 1; // 调整right
}else{
return mid; // 找到了直接return
}
}
return -1; // 未找到返回-1
}
};
27. 移除元素
力扣题目连接：https://leetcode.cn/problems/remove-element/description/
代码随想录讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
对于移除元素暴力解就是双for循环。但是这道题要学会双指针来求解。需要剔除的数被后面的不需要进行剔除的数进行覆盖的思想，来剔除目标数字。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int idx = 0; // 用于记录下一个需要填充值的索引位置
int len = nums.size(); // 整个数组长度
for(int cursor = 0; cursor < len; cursor++){ // cursor的作用就是从头到尾遍历一遍数组
if(nums[cursor] == val) { // 如果当前遍历的数与需要剔除的数一致，说明这是需要被剔除的数，则不需要存到nums中了，直接跳过就行
continue;
}
nums[idx++] = nums[cursor]; // 如果不一致的话，就是需要保留的数字，那么这个数字就需要填充到idx位置，然后idx再往后移一个位置
}
return idx; // 最后idx就是剔除后的数组长度
}
};
