代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素

二分查找

题目链接：https://leetcode.cn/problems/binary-search/

文章讲解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html

视频讲解：https://www.bilibili.com/video/BV1fA4y1o715

我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。

区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：

• while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
• if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

代码如下：

/*** @description: 二分查找* @author: blblccc* @date: 2022/12/30 17:50*/
public class BinarySearch {public int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;int mid = 0;while (left <= right) {mid = left + (right - left) / 2;if (nums[mid] > target) {right = mid - 1;} else if (nums[mid] < target) {left = mid + 1;} else {return mid;}}return -1;}q
}

移除元素

题目链接：https://leetcode.cn/problems/remove-element/
文章讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针：指向更新 新数组下标的位置

/*** @description: 移除元素* @author: blblccc* @date: 2022/12/30 20:34*/
public class RemoveElements {public int removeElement(int[] nums, int val) {int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.length; fastIndex++){if (nums[fastIndex] != val){nums[slowIndex] = nums[fastIndex];slowIndex++;}}return slowIndex;}
}