二分查找
二分查找是基础的搜索算法之一，对应leetcode704题题目描述如下：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入:nums= [-1,0,3,5,9,12],target= 9 输出: 4 解释: 9 出现在nums中并且下标为 4
示例 2:
输入:nums= [-1,0,3,5,9,12],target= 2 输出: -1 解释: 2 不存在nums中因此返回 -1
本题是二分搜索经典模版题，难度不是特别的大，但在写代码的过程中你是否也有过和我一样的疑惑是还是
以及l
与
如何更新的问题。其实这些问题出现的根源在于首次接触时，并没有注意到区间定义的区别导致的代码书写细节上的不同，因此本文讲给出两种定义（左闭右闭与左闭右开）
第一种写法，我们定义 target 是在一个在左闭右闭的区间里，即[left, right] 由于定义target在[left, right]区间，所以有如下两点：
- while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
- if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
- 对应下图（摘自代码随想录网站）
- 对应代码：
-
int search(int* nums, int numsSize, int target) { int l=0,r=numsSize-1; while(l<=r)//左闭右闭写法 { int mid=(l+r)/2; if(nums[mid]==target)return mid; else if(nums[mid]<target)l=mid+1; else r=mid-1; } return -1; }
第二种写法：如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right) ，那么二分法的边界处理方式则截然不同。
有如下两点：
- while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
- if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]
具体如下图所示（摘自代码随想录网站）
对应代码：
int search(int* nums, int numsSize, int target)
{
int l=0,r=numsSize;
while(l<r)//左闭右开写法
{
//l<r ：理解为只有l<r,左闭右开的区间定义才合法
int mid=(l+r)/2;
if(nums[mid]==target)return mid;//查找成功
else if(nums[mid]<target)l=mid+1;//由于区间定义为左闭右开，而执行此更新时,
//mid处对应的值已比较，故此处为mid+1
else r=mid;//由于区间定义为左闭右开，这里如果mid-1则比较区间中不包含mid-1，可能导致错误
}
return -1;
}移除元素
题目描述：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
输入：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]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,3,0,4] 解释：函数应该返回新的长度5, 并且 nums 中的前五个元素为0,1,3,0,4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。 提示：
0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100
本题有两种方法，暴力方法这里不在叙述（每次发现一个符合要求的元素，将后面所有元素前移以为，对于每个符合条件元素重复此操作，直至完成，对应时间复杂度为）接下来重点介绍快慢指针法：
双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
定义快慢指针
- 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
- 慢指针：指向更新 新数组下标的位置
具体过程如下动图所示（摘自代码随想录网站）
代码实现：
int removeElement(int* nums, int numsSize, int val) {
int slow = 0,fast = 0;
//?? 快指针指向的是新数组中元素的值，而slow指针表示的
//是新数组中元素。及新数组由nums[slow]构建
for(fast=0;fast<numsSize;fast++)
{
if(nums[fast]!=val)
{
nums[slow++]=nums[fast];
}
}
return slow;
}
