代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素

一、704. 二分查找

题目链接：https://leetcode.cn/problems/binary-search/description/
文章讲解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
视频讲解：https://www.bilibili.com/video/BV1fA4y1o715

1.1 初见思路

有序数组找目标值–》二分法
二分法需注意点：范围区间，左闭右开 或 左闭右闭

1.2 具体实现

class Solution {
    public int search(int[] nums, int target) {
        //左闭右开
        int left=0;
        int right = nums.length-1;
        int mid=0;
        while(left<right){
            mid = left+(right-left)/2;
            if(nums[mid]<target){
                left=mid+1;
            }
            else if(nums[mid]>target){
                right=mid;
            }
            else{
                return mid;
            }
        }
        return -1;
    }
}

1.3 重难点

• while循环的循环条件是< 还是 <=？
• 给left 和 right 赋值时，是否应该+1，原值，还是-1？
  上述两点重点就在于对 取值区间的选择，左闭右开/左闭右闭
  写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。

对区间的选择的理解
[图片]

二、 27. 移除元素

题目链接：https://leetcode.cn/problems/remove-element/
文章讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP

2.1 初见思路

采用双指针的方式，把所有需要删除的val都移到数组的最后。
左指针指向等于val的值，右指针指向不等于val的值，swap()，同时计数+1，最后返回计数。

2.2 具体实现

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

}

2.3 重难点

解题过程中一直无法通过，最终发现问题就出在while的循环条件上！
循环条件是<=