## LeetCode 704-二分查找
-题目描述：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，
-写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，
写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
-题目链接：leetcode.cn/problems/bi…
-解题思路：
用二分法。从中间开始查找，根据target值的大小改变left和right的值
-二分法使用条件：
1.查找的是有序的数组
2.没有重复的元素
方法1: 左闭右闭区间 [left, right]
class Solution { public: int search(vector<int>& nums, int target)
{ int left =0;
int n =nums.size();
int right = n-1;
while(left<=right)
{
int middle=left+(right - left)/2;
if(nums[middle]<target) { left =middle +1; }
else if(nums[middle]>target) { right = middle-1; }
else return middle; //数组中找到目标值，直接返回下标
}
return -1; //未找到目标值，返回-1
}
}; 思考：
1.为什么right=n-1呢，因为当左闭右闭时，能够定义target在[left,right]这个区间里。
2.同时在左闭右闭时，left ==right是有意义的，所以while条件是left<=right。
3.为什么这边middle不用(right+left)/2讷？因为这样的话可能会溢出。
方法2: 左闭右开区间 [left, right）
class Solution {
public:
int search(vector<int>& nums, int target) {
//采用左闭右开的方法
int left =0;
int right = nums.size(); //因为采用左闭右开的方法，target在[left,right)的范围内，并且
// right的位置是没有效果的
while(left<right) //此时若left==right没有意义
{
int middle= left + ((right-left)>>1 ); //用右移动运算符代替除以2
if(nums[middle]<target)
{
left = middle+1;
}
else if(nums[middle]>target)
{
middle=right; //因为右边为开 target在[left,right)范围内
}
else // nums[middle]==target
{
return middle;
}
}
return -1; //未找到值返回-1
}
};
总结：利用二分法主要注意到是闭区间和开区间的取值，以及循环是否应该带等号；取middle值时要判断是否要+1；
## LeetCode 27-移除元素
题目描述：给你一个数组 nums 和一个值 val，你需要 **原地** 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
题目链接：leetcode.cn/problems/re…
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案
方法1: 双指针法
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left =0;
int right =0;
int n = nums.size();
for(;right<n;right++)
{
if(nums[right]!=val)
{
nums[left++]=nums[right];
}
}
return left;
}
};思考：
利用快慢指针的方法，如果右指针不等于Val，
那么将右指针 right 指向的元素复制给左指针 left ,同时将左右指针同时右移；
如果右指针指向的元素等于Val,
那么left指针不动，right指针向右移动一位
当遍历完后，left的值就是整个数组的长度
方法2: 双指针法优化
class Solution {
public:
// 左闭右开
int removeElement(vector<int>& nums, int val) {
int left =0;
int right = nums.size();
while(left<right) //left==right时退出循环
{
if(nums[left]==val)
{
nums[left]=nums[right-1]; //将right指针指向的值直接覆盖
// right-1的原因是数组从0开始，right-1即为最后一位
right--; //覆盖后数组长度减少，right自减1
}
else
{
left++;
}
}
return left;
}
};class Solution { public: int removeElement(vector<int>& nums, int val) { //双指针优化-左闭右闭 int left =0; int right = nums.size()-1; while(left<=right) { if(nums[left]==val) { nums[left]=nums[right]; right--; //长度减一 } else left++; } return left; } };
思考：
考虑到题目条件为“元素的顺序可以改变”
如果left指针指向的元素等于val，
我们可以把right指针指向的值直接复制到左指针的位置，然后right指针左移一位；
如果赋过来的值也是val，
可以继续把right的值赋过来（注意这是right指针已经向左移动一位）；
当left和right重合时，左右指针遍历完数组中所有元素
**与方法一相比，方法二避免了需要保留元素对重复赋值**方法二中的左闭右开和左闭右闭的区别仅仅是while中的循环不同。
方法3: 暴力解法
文章来源：https://www.toymoban.com/news/detail-586216.html
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
for(int i=0;i<n;i++)
{
if(nums[i]==val)
{ //发现需要移除的元素，数组集体向前移动一位
for(int j=i+1;j<n;j++)
{
nums[j-1]=nums[j];
}
i--; //i后面的数组都向前移动，i也要向前移动一位
n--; //数组长度也要减少一位
}
}
return n;
}
};
**总结**
双指针的做法还是非常常见的，要学会灵活运用快慢指针文章来源地址https://www.toymoban.com/news/detail-586216.html
到了这里，关于# - LeetCode 704-二分查找 ｜LeetCode 27-移除元素的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
