704.二分查找
思路
利用 middle 去寻找 target
-
前提条件：
这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，二分查找法返回的元素下标可能就不唯一，这些都是二分法的前提，以后看到题目描述后可以先想一想是否符合二分查找的条件。
-
难点：
二分查找的难点在于边界问题，很容易思路混乱。例如到底是
while(left <= right)还是while(left < right)，到底是right = middle - 1还是right = middle呢？ -
解决方式：
二分法的区间一般有两种定义方式，左闭右闭即 [left, right] ，左闭右开即 [left, right) 。
第一种：左闭右闭
区间的定义就决定了二分法的代码应该怎么写，因为定义 target 在 [left, right] 区间，所以有如下两点：
while (left <= right)要使用 <= ，因为left = right是有意义的，例如[1, 1]。if(nums[middle] > target)right 要赋值为middle - 1，最初 right 的赋值为nums.length - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的区间右结束下表一定是middle - 1
代码如下：
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 定义target在左闭右闭区间里，[left, right]
while (left <= right) {
int middle = left + (right - left) / 2; // 防止边界溢出
if (nums[middle] > target) {
right = middle - 1; // target 在左区间里，所以 [left, middle - 1]
} else if (nums[middle] < target) {
left = middle + 1; // target 在右边界里，所以 [middle + 1, right]
} else {
return middle; // 找到target，直接返回下标
}
}
return -1; // 没有找到target，返回-1
}
}
第二种：左闭右开
边界处理方式截然不同，如下两点：
while(left < right)，这里使用 < ，因为left == right在区间 [left, right) 是没有意义的。例如 [1, 1) ，这是违法的。if(nums[middle])right 更新为 middle ，最初 right 的赋值为nums.length，因为当前nums[middle]不等于 target ，而 寻找区间又恰为 左闭右开 区间，所以 right 更新为 middle ，下一个查询区间也不会去比较 nums[right]
代码如下：
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length; // 定义target在左闭右闭区间里，[left, right)
while (left < right) {
int middle = left + (right - left) / 2; // 防止边界溢出
if (nums[middle] > target) {
right = middle; // 在左区间里，所以 [left, middle)
} else if (nums[middle] < target) {
left = middle + 1; // 在右区间里，所以 [middle, right)
} else {
return middle; // 找到target，返回
}
}
return -1;，// 未找到target，返回-1
}
}
27.移除元素
思路
不需要考虑数组中超出新长度后面的元素。
数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
双指针法
双指针法（快慢指针）：通过一个快指针和满指针在一个for循环下完成两个for循环的工作。
定义快慢指针：
- 快指针：寻找新元素的指针，通过遍历数组寻找出不含目标元素的数组
- 满指针：用来在原数组的基础上生成新数组
双指针法在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针。
代码实现
- 时间复杂度：O(n)
- 空间复杂度：O(1)
class Solution {
public int removeElement(int[] nums, int val) { //同侧开始
int slow = 0;
for (int fast = 0;fast < nums.length;fast++) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
}
class Solution {
public int removeElement(int[] nums, int val) { //两侧开始
int left = 0;
int right = nums.length - 1;
while (left <= right) {
if (nums[left] == val) {
nums[left] = nums[right];
right--;
} else {
left++;
}
}
return left;
}
}