704. 二分查找
leetcode：704. 二分查找
文档讲解：704. 二分查找
视频讲解：《代码随想录》算法视频公开课：手把手带你撕出正确的二分法
本题考查基础的二分查找，和暴力解法不同，根据数组的有序性，折半地缩小查找空间，达到快速查找的目的。
二分查找的思想很简单，但是在处理边界上容易出问题，归根结底是对搜索空间的定义不明确，导致查找时漏掉或者多加了元素。
常用的查找空间有两种，一种是左闭右闭，一种是左闭右开，现在分别对这两种实现方法做详细的实现。
左闭右闭
即区间内的元素全是未确定的元素，确定的元素不会在这里面（如要目标元素和一定不是目标的元素）。
class Solution {
public int search(int[] nums, int target) {
// 因为数组是有序的，所以小于最小值或大于最大值的元素一定不在数组中
if (target < nums[0] || target > nums[nums.length - 1]) return -1;
// 注意：左闭右闭区间，所以 right 起始为数组的最后一个元素
int left = 0;
int right = nums.length - 1;
// 注意：这里是小于等于，因为 left == right 时，搜索区间只有一个元素，
// 仍然是合法的搜索区间，可能这一个元素就是目标值
while (left <= right) {
// 获取中间值，避免大数相加溢出
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
// 目标值在右边，要舍弃另一半查找空间，因为 nums[mid] 已经确定不是目标值，
// 所以 mid 不应该被包含在区间内，因此 left 直接取 mid 的下一个位置
left = mid + 1;
} else if (nums[mid] > target) {
// 目标值在左边，要舍弃另一半查找空间，因为 nums[mid] 已经确定不是目标值，
// 所以 mid 不应该被包含在区间内，因此 right 直接取 mid 的前一个位置
right = mid - 1;
}
}
return -1;
}
}左闭右开
区间的定义和左闭右闭是一样的，但是因为右边是开区间，所以对 right 指针的处理会有些不同。
class Solution {
public int search(int[] nums, int target) {
// 因为数组是有序的，所以小于最小值或大于最大值的元素一定不在数组中
if (target < nums[0] || target > nums[nums.length - 1]) return -1;
// 注意：左闭右开区间，right 指向的元素并不在区间内，因此 right 起始为 nums.length
int left = 0;
int right = nums.length;
// 注意：这里是小于，因为是左闭右开区间，当 left == right 时，搜索区间为空，不应该再去循环了
while (left < right) {
// 获取中间值，避免大数相加溢出
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
// 和左闭右闭一样
left = mid + 1;
} else if (nums[mid] > target) {
// 因为是左闭右开区间，right 指向的是不在区间内的元素，
// 此时的 nums[mid] 刚确定完不是目标值，要从区间内排除，因此将 mid 赋值给 right
// 且 mid - 1 可能是目标值，因此需要在区间内
right = mid;
}
}
return -1;
}
}27. 移除元素
leetcode：27. 移除元素
文档讲解：27. 移除元素
视频讲解：《代码随想录》算法视频公开课：数组中移除元素并不容易
题目要求在原数组上修改，所以是在考察数组的基本操作，因此只能采用覆盖的方法，因为数组的长度是固定的。
暴力解法
双层 for 循环遍历元素，如果是目标值，就将目标值后面的元素挨个往前覆盖，要注意循环结束的条件。
class Solution {
public int removeElement(int[] nums, int val) {
int len = nums.length;
// 随着目标值不断的覆盖，遍历的终点在不断前移，
// 因此要 "提前" 结束循环，不能再遍历到 nums.length
for (int i = 0; i < len; i++) {
if (nums[i] == val) {
// 找到目标值，后面的元素往前覆盖，
// 注意内层循环的结束条件是 len - 1，防止访问 j + 1 时越界
for (int j = i; j < len - 1; j++) {
nums[j] = nums[j + 1];
}
// 重点：删掉一个元素，长度 - 1
len--;
// 重点：因为当前元素已经被后面的元素覆盖了，此时的 i 指向的是覆盖的那个元素，
// 下一轮循环还要对它做判断，所以 i 回退一次
i--;
}
}
// 遍历结束，len 就是删除指定元素后剩余元素的数量
return len;
}
}双指针
暴力解法的时间复杂度是 O(n^2)，时间花费在了挨个移动元素上，所以优化的重点就在这里，能否一次遍历解决问题。
双指针的思路是定义两个指针，初始都指向数组的第一个元素，left 指针表示该指针之前的元素都是非目标值，right 指针用来遍历数组，如果当前遍历的元素不是目标值，则将nums[right] 赋值给 nums[left]，且 left、right 同时后移，如果当前遍历的元素是目标值，则 left 停顿，right 继续后移，重复上述循环。
class Solution {
public int removeElement(int[] nums, int val) {
int left = 0, right = 0;
while (right < nums.length) {
// 重申一下，left 表示该位置之前的元素都是要留下的元素，不包含要删除的元素
// 所以这里要处理不等于目标值的元素
if (nums[right] != val) {
nums[left] = nums[right];
left++;
}
right++;
}
return left;
}
}这个双指针的思想很巧妙，一个指针用来控场（存储），一个指针用来遍历，符合条件的元素就扔进存储中，存储不断扩大，left 不断后移。
交流
交流一
群友关于 “移除数组元素” 提出了个问题，问该题使用暴力解法的时候，为什么解法 2 会通过，解法 1 会超时。如果是因为结束条件是 nums.size() 的话，那么第二层循环的 j 为什么可以用 nums.size()，而不是size？
// 解法 1
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
// i 的结束条件是 nums.size()
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == val) {
// j 的结束条件也是 nums.size()
for (int j = i; j < nums.size() - 1; j++) {
nums[j] = nums[j + 1];
}
size--;
i--;
}
}
return size;
}
}// 解法 2
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
// i 的结束条件是 size
for (int i = 0; i < size; i++) {
if (nums[i] == val) {
// j 的结束条件也是 nums.size()
for (int j = i; j < nums.size() - 1; j++) {
nums[j] = nums[j + 1];
}
size--;
i--;
}
}
return size;
}
}我按他的解法画图执行了一下，发现当测试用例的最后一个元素是要删除的元素时代码会执行超时，看下图分析：
蓝色箭头表示外层循环，每一次发现目标值都会将其后面的元素挨个往前覆盖，然后后面多出一个“越界”的元素（即方块中的元素）。外层循环按理来说应该在 3 位置结束，但因为解法 1 中外层循环的结束条件是 i < nums.size()，因此外层会继续往后遍历，如图中下面蓝色的部分，但是后面的元素都是目标值，i 也一直会回退到当前目标值的位置，导致无限循环。导致无限循环的原因是测试用例的最后一个元素是要删除的元素，如果把最后的 2 去掉，解法 1 也能通过。
上面的分析能够解释解法 1 为什么超时，但还不是问题的重点。问题的重点是外层循环的结束条件不应该是 i < nums.size()，因为随着目标值的不断删除，数组的长度会“变小”，后面要被遍历的元素会不断前移，因此应该按照现有的数组长度结束循环。
那么为什么内层循环的结束条件可以是 j < nums.size() 呢？因为内层循环的作用不是遍历，而是将目标值后的元素挨个往前覆盖，即便是“越界”（超出当前数组的长度）了，也不会影响当前数组长度内的元素，因为它的作用就是覆盖。虽然没影响，但是毕竟还是多执行了几次无意义的覆盖，所以内层循环的结束条件也应该是 j < 当前数组的长度。
总结，我们操作的是 当前数组长度范围内 的元素，删除目标值后，数组长度会变小，后面的元素也都往前移动了，那些 “越界” 的元素就不用管了，内外层循环不需要去遍历它们，因此循环结束条件都应该是当前数组的长度。
交流二
群友提了关于 “二分搜索” 的问题，问既然理论上四种区间都可以，为什么左开右闭区间会超时呢？代码如下：
class Solution {
public int search(int[] nums, int target) {
if (target < nums[0] || target > nums[nums.length - 1]) return -1;
// 左开右闭区间
int left = -1, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
return -1;
}
}拿题目给的测试用例画图试了下：
看来是 mid 搞得鬼，左开右闭区间下，把 mid 的取值改为向上取整就可以了，还不清楚为什么。
int mid = (int)(Math.ceil((left + right) / 2.0));