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是下一个元素待填入位置