LeetCode 704:二分查找
题目链接：二分查找
二分法很常见，但是在while循环里的条件与后续left/right指针的变化逻辑有很大关联，很容易出现思路正确，代码怎么也无法通过的情况，浪费时间。
class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
int left = 0;
int right = len-1;
while(right>=left){
int index = (left+right)/2;
if(nums[index]==target){
return index;
}else if(nums[index]>target){
right = index-1;
}else{
left = index+1;
}
}
return -1;
}
}
这里采用的是左闭右闭的思路区来写的
左闭右闭指的是，在新划分出来的区间中，left和right都是需要下一步比较的[left,right]，因此：
-
left==right时，还不能跳出循环，闭区间内仍然有一个元素等待比较，while里面的条件为right>=left； -
left和right的每一次更新都是index+1，index-1, 因为index已经被比较过，不可以再进入下一次比较的区间内
LeetCode 27： 移除元素
题目链接：移除元素
这道题采用的是双指针+swap的思路来做的，踩了很多坑，针对这一种写法，有以下几点注意：
-
while里面的条件尽量不要写!=，容错率大大降低，很容易死循环！ - 处理顺序的问题，先做主要逻辑，即判断可以交换后交换值，再往下寻找
- 对于这种前后双指针向中间靠的问题仍然需要进一步总结，在这里真的踩了很多坑，每次都稀里糊涂的过了
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[right]!=val){
nums[left] = nums[right];
nums[right] = val;
}
else{
if(nums[left]!=val){
left++;
}
if(nums[right]==val){
right--;
}
}
}
return left;
}
}
这道题还有一种更加清晰的思路：快慢指针方法
用快指针寻找非val值，用慢指针一步一步覆盖原数组里面的值
class Solution {
public int removeElement(int[] nums, int val) {
int slow = 0;
int fast = 0;
while(fast<nums.length){
if(nums[fast]!=val){
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
}
注意return的是slow，而不是slow+1，因为slow是下一个元素待填入位置
