数组基础：二分查找与移除元素（快慢指针）

二分查找

二分查找是基础的搜索算法之一，对应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 <= 100
• 0 <= nums[i] <= 50
• 0 <= 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;
}

?