704.二分查找
题目链接：704. 二分查找 - 力扣（LeetCode）
文档讲解：代码随想录 (programmercarl.com)
视频链接：手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找_哔哩哔哩_bilibili
状态：一刷；
1.看到题目第一思路
第一思路：设立左右指针，比较target与middle的值
if target=middle ,return middle
if target<middle,说明 left<=target<middle,更新right = middle-1，更新查找范围[left,right]
if target>middle 说明middle<target<=right,更新left=middle+1,更新查找范围[left,right]
2.看完代码随想录想法
二分法的前提条件：有序数组，且数组无重复元素
二分法区间定义：左闭右闭[ left , right ]，左闭右开[ left , right )
优化middle计算：
middle = left+((right-left)>>1) 防止溢出,等同于（left+right)/2;
调整middle计算式的位置，放在循环里先进行计算。
判断循环条件方式：
当区间定义为[ left , right ],此时left==right依然有效，即<=
当区间定义为[ left , right )，此时left==right 无效，即<
3.实现遇到的困难
困难点：指针边界问题，查找范围为[left,right],即左闭右闭区间
初值：left=0,right=nums.length-1,middle=(left+right)>>2;
循环条件：假设数组只有一个值，则left=right=middle,那么条件为left<=right
4.代码
在更新left，right指针时要把握边界指针是否在可判定区间内
/**
* 代码随想录左闭右闭
*/
class Solution1 {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length-1;//定义target在左闭右闭的区间里，[left,right]
while(left<=right){ //当left==right时，区间[left,right]依然有效，所以用<=
int middle = left +((right-left)>>1);//防止溢出，等同于(left+right)/2;
if(target==nums[middle])
return middle; // 数组中直接找到目标值，返回下标
else if(target<nums[middle]){
right = middle-1; //target在左区间 [left,middle-1]
}else{
left = middle+1; //target在右区间，[middle+1,right]
}
}
return -1; //遍历后找不到，返回-1
}
}
/**
* 代码随想录左闭右开区间
*/
class Solution2{
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length; //定义target在左闭右开区间，[left，right),即实际查找范围是[left,right-1]
while(left<right){ //当left==right时,[left,right)是无效区间，所以用<
int middle = left+(right-left)>>1;
if(target==nums[middle])
return middle;//找到目标值target，返回下标
else if(target<nums[middle]){
right=middle;//target在左区间，[left,middle)
}else{
left=middle+1;//target在右区间，[middle+1,right)
}
}
return -1;
}
}27.移除元素
题目链接：27. 移除元素 - 力扣（LeetCode）
文档链接：代码随想录 (programmercarl.com)
视频链接：数组中移除元素并不容易！ | LeetCode：27. 移除元素_哔哩哔哩_bilibili
状态：一刷
1.看到题目第一思路
从前往后遍历，如果num[i]==k,那么将这个元素往后的元素往前移动一个位置，覆盖掉这个元素。
引入统计相同元素k的计数变量count，返回nums.length-count
2.看完代码随想录想法
数组的特点：数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
暴力法：即使是暴力算法也比我优雅的多。直接用size=nums.length就把数组的逻辑大小规定清楚了，就不用原始数组大小和count等等算边界了，遇到覆盖直接size--即可，解决逻辑缩小的问题，同时用size作为右边界即可。
在编写过程中我也考虑到了数组逻辑大小缩小，指针回退的问题，但实现起来就很惨不忍睹。
双指针法：定义快慢指针
快指针：寻找新数组的元素，新数组就是不含有目标元素的数组
慢指针：指向更新新数组下标的位置
判断条件究竟是!=还是==就有很大区别。这里用 != 逻辑更简单，只需要复制即可
3.实现遇到的困难
依旧是数组边界问题。
首先每次往左覆盖一个单位，数组大小逻辑上是减1的，也就是右边界大小-1.
所以right指针更新式为right = nums.length - count - 1;这里需要先更新式子，再count++。因为只有覆盖之后才能缩小右边界。
4.代码
class Solution2{
public int removeElement(int[] nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0;fastIndex<nums.length;fastIndex++){//如果是剔除元素val，则fastIndex指针持续向前，直到找到不是的元素为止，复制给新数组。
if(nums[fastIndex]!=val){//如果不是剔除元素val，那么新数组的元素复制fastIndex所指元素
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;//经过最后一次++后，slowIndex大小等于新数组大小
}
}35. 搜索插入位置
题目链接：35. 搜索插入位置 - 力扣（LeetCode）
文档链接：代码随想录 (programmercarl.com)
视频链接：
状态：一刷
不变量是[ left , right ]
每次循环数组大小-1，所以当left==right时不会出现死循环的情况。
正常跳出循环的条件一定是target==nums[middle]，当找不到跳出循环right<left,并且差一个单位.
分别处理如下四种情况：
目标值在所有元素之前：[0 ,-1]
目标值等于数组某个元素 return middle
目标值插入数组中某个元素位置：[left right],return right+1
目标值在所有元素之后的情况[left , right] return right+1;
class Solution{
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while(left<=right){
int middle = left+((right-left)>>1);
if(target==nums[middle])
return middle;//数组中存在该数值，返回其索引
else if (target<nums[middle]) {
right=middle-1;//target在左区间，[left,middle-1]
}else{
left=middle+1;//target在右区间，[middle+1,right]
}
}
return right+1;
}
}
今日感想
学习的时候慢吞吞的，花了一下午，再写LeetCode35题时，发现还是对二分查找理解不深刻。
利用循环不变式写出正确的二分查找及其衍生算法 – KelvinMao Blog
