704. 二分查找

这个之前有写过，最重要的就是把握住要去搜索的区间的形式，包括左闭右闭以及左闭右开两种

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        while(left < right){  // 左闭右开的版本，结果存储在[left, right)中，因此如果最终left >= right，就意味着没有找到结果
            int mid = (left + right) / 2;
            if(nums[mid] > target) { right = mid; }  // 结果在区间[left, mid)
            else if(nums[mid] == target){ return mid; }  
            else{ left = mid + 1; }  // 结果在区间[mid + 1, right)
        }
        return -1;
    }
}

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right){  // 左闭右闭的版本，结果存储在[left, right]中，只有left > right，意味着没有找到结果
            int mid = (left + right) / 2;
            if(nums[mid] > target) { right = mid - 1; }
            else if(nums[mid] == target){ return mid; }
            else{ left = mid + 1; }
        }
        return -1;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

思想还是二分查找，但分为两个步骤，分别去找最左边的和最右边的。二分查找我觉得还是先以一种方法去做吧，比如就只用左闭右闭的方式，这样可以避免自己混乱。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[] {findLeft(nums, target), findRight(nums, target)};
    }

    public int findLeft(int[] nums, int target){
        int left = 0, right = nums.length - 1;
        int ans = -1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) { left = mid + 1; }
            else if(nums[mid] == target) { 
                ans = mid;
                right = mid - 1;  // 找到target后，因为要找最左边的，所以搜索空间向左压缩
            }else{
                right = mid - 1;
            }
        }
        return ans;
    }

    public int findRight(int[] nums, int target){
        int left = 0, right = nums.length - 1;
        int ans = -1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) { left = mid + 1; }
            else if(nums[mid] == target) { 
                ans = mid;
                left = mid + 1;  // 同理，向右压缩搜索区间
            }else{
                right = mid - 1;
            }
        }
        return ans;
    }
}

27. 移除元素

我的直观想法就是每遇见一个等于val的元素，就将其换到数组的末尾，此时换过来的元素还没有判断，因此left不动，但换到结尾的元素一定要被删除，因此right--；遇见不等于val的，不需要交换，left++即可；最终left会停止在数组最后一个合法元素的下一个元素，其下标刚好为最终数组的长度

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0, right = nums.length - 1;
        while(left <= right){
            if(nums[left] == val){
                nums[left] = nums[right];
                nums[right] = val;
                right -= 1;
            } else{
                left += 1;
            }
        }
        return left;
    }
}

今天这些题自己之前有做过，所以做起来还算得心应手，没有完全忘掉。但还是一点，刚开始二分查找就先记得用左闭右闭的方法去做，其实基本上大部分的题就套用模板，不要给自己增添别的负担最好。