代码随想录第一天 704二分查找 27移除元素

本文主要是介绍代码随想录第一天 704二分查找 27移除元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一题：二分查找

原题链接704. 二分查找 - 力扣（LeetCode）

思路：

最经典的二分查找问题：

题目中的前提是有序数组，同时还强调数组中无重复元素，因此便可以使用二分查找

二分的逻辑也很简单，取中间位置的下标，判断下标处的值是否等于目标值，如果下标处的值小于target，则将左边界更新为mid + 1，反之右边界更新为mid + 1。

思路比较简单就是要考虑边界问题，有些细节没注意到就会导致程序运行失败

首先我们定义target是在一个左闭右闭的区间里，也就是[left, right];这点很关键：原因如下：

此时我们需要left == right 的情况，当数组中只有一个数字时，我们需要让逻辑进入我们的while循环中并返回结果否则会输出-1；

原因二：当我们判断if(nums[mid] < target)时，我们需要更新左边界，此时需要将left = mid + 1；因为是左闭右闭因此nums[mid]的值肯定不是target，所有直接将左边界更新为mid + 1即可。

下面给出代码

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left <= right){int mid = (left + right) / 2;if(nums[mid] < target){left = mid + 1;}else if(nums[mid] > target){right = mid - 1;}else{return mid;}}     return -1;}
};

Carl的解答中提高mid = left + (right - left) / 2; 是为了防止溢出。

第二题：移除元素

原题链接：27. 移除元素 - 力扣（LeetCode）

思路：

双指针法：

首先我们先定义一根慢指针slowIndex用于计数，作为返回值返回同时也作为更新数组下标的索引。然后我们定义快指针fastIndex遍历整个数组，此时我们需要判断快指针是否跟要移除的元素相同，如果不相同则nums[slowIndex] = nums[fastIndex];同时更新慢指针的索引，slowIndex++；一一旦快指针在遍历的过程中遇到了要移除的元素时，便直接跳过该元素，fastIndex指向下一个元素，slowIndex则留在原地等待。

下面给出代码：

class Solution {
public:int removeElement(vector<int>& nums, int val) {int slowIndex = 0;for(int fastIndex = 0; fastIndex < nums.size(); fastIndex++){if(val != nums[fastIndex]){nums[slowIndex++] = nums[fastIndex];}}return slowIndex;}
};

Carl：