代码随想录算法训练营Day1 : 704.二分查找、27.移除元素

二分查找：

题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

题目链接：704.二分查找

卡哥的视频讲解：把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找

二分法使用前提：

有序数组或列表：二分法要求在查找的数据结构中元素按照某种顺序有序排列，通常是升序排列。如果数组或列表没有排序，需要先对其进行排序，否则无法使用二分法进行查找。

目标元素存在：二分法适用于在有序数组或列表中查找目标元素是否存在，或者查找目标元素的位置。如果目标元素不在数组或列表中，二分法无法成功找到目标元素。

随机访问：二分法要求能够通过索引或指针以O(1)的时间复杂度访问数组或列表的任意位置。这通常意味着数据结构需要支持随机访问，比如数组。

刚看见二分法的时候，有一个大概的思路，但是很多细节都没注意到，比如要先排序，以及边界的取值，是开还是闭

代码示例：

示例一：左闭右闭写法

示例二：左闭右开写法

总结：

1.>> 是右移位操作符，它将左操作数向右移动指定的位数。在这里，right - left 表示当前搜索范围的长度，right - left >> 1 将长度右移一位，相当于将长度除以2，得到搜索范围的一半。然后再加上 left，得到中间位置 mid。

这种写法与普通的 (left + right) / 2 求中间位置的写法相比，可以避免在大数相加时可能导致的溢出问题，同时也更为高效。因为右移位操作符的性能比除法运算更高，尤其在一些硬件上会被优化为位运算。

2.在写范围的时候，是根据是否包含数组的边界元素来确定的。

3.闭或者不闭的区别就在于初始定义，循环条件和mid的取值。

leetcode提交记录：

移除元素：

题目：

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

题目链接：27.移除元素

卡哥的视频讲解：数组中移除元素并不容易！ | LeetCode：27. 移除元素

自己的思路：再新建一个数组，把要删除数字以外的元素填入新数组

知识点：

数组下标都是从0开始的。
数组内存空间的地址是连续的
数组是存放在连续内存空间上的相同类型数据的集合。所以删除元素不能直接删除，而是要覆盖。

解题思路：

用双指针的思想，定义快慢两个指针，快指针用来寻找新数组的元素 ，新数组就是不含有目标元素的数组，一旦搜索到就将其下标值传给慢指针，慢指针用于指向更新新数组下标的位置。

代码示例：

代码详解：

1.定义两个指针 slow 和 fast，初始都指向数组的起始位置。

2.使用 fast 遍历整个数组，逐个检查数组中的元素。

3.如果当前元素 nums[fast] 不等于要移除的值 val，则将当前元素放置到 slow 的位置，然后将 slow 向后移动一位。

4.如果当前元素等于 val，则不做任何操作，继续遍历下一个元素。

5.最终返回 slow 的值，即移除元素后数组的长度。

总之，该函数通过双指针的方法在原地修改数组，将不等于目标值的元素移动到数组的前面，并返回移除后数组的长度。但是需要指出的是，当前代码中没有正确处理等于目标值的情况，因此会存在问题。应该在条件判断中增加对等于目标值的情况的处理，例如在遇到 nums[fast] == val 时，快指针 fast 前进，而慢指针 slow 不动，这样才能正确移除目标值。

leetcode提交记录：