1,3, 今天是录友集训营第一天，学习的内容是数组，完成一篇数组基础知识的文章学习以及*****。题目都已经做完，写点做后感，总结一下，也是完成每日打卡的任务。

704.二分查找

这题就是简单且经典的二分题，首先看题目就能确定出这题就是要用二分法，看见题中有序数组并且数组元素不重复，二分法就八九不离十了。然后按照Carl的二分查找的思路，确定好查找区间就好，是[left,right]还是[left,right)。有时候做二分懵逼很大原因就是查找区间混乱，就确定好二选一就可以，都是套路。如果是[left,right]，就是while(left >= right)，里面if(nums[mid] > target)中就是right = mid - 1，因为nums[mid]一定不是tagert，所以我们有时候就在纠结这里right是mid还是mid-1，我们的查询区间为[left,right]，right是有效地，会被查询到的，存在left == right的情况，所以right就为mid-1。同理，当查找区间为[left,right)，此时while(left > right)，if(nums[mid] > target)中就是right = mid，因为right是无效的，查到left == right就已经不成立了。

两种写法大家可以固定使用一种，我就习惯用[left,right]。

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

        return -1;
    }

}

35.搜索插入位置

这题看见排序数组和无重复，还是二分查找。根据题目要求，你的target在数组中会有四种出现的位置，比如nums = {1,3,5,6}，target可能在数组右侧，可能在左侧，可能在数组里并且存在，还可能在数组里但是不存在。

举几个例子

1.在右侧，target = 7

这种情况下，一直是left向右移动，直到left越界，此时要插入的位置就是right + 1

2.在左侧，target = 0

这种情况下，right一直左移，直到right越界，此时要插入的位置仍是right+1

3.在数组内但不存在，target = 2

此时，先按照二分法查找。第一轮查过后数组为{1,3}，第二轮查过后数组为{1}，再查一次left越界，此时right = 0，要插入的位置是1，所以还是right + 1

4.在数组内且存在，target = 3

二分法直接出即可

综上所述，可以归为两种return情况，一是target存在，用二分法查找到返回即可。另一种是其他三种情况整合为一种，不符合二分查找就return right + 1即可。

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while(left <= right){
            int mid = left  + (right - left)/2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }

        return right + 1;
    }
}

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

依然是二分法，我需要找到元素的第一个位置和第二个位置，比如在nums = [5,7,7,8,8,10]中，边界为[3,4]，所以我们可以先找到不包含查找元素的左边界2以及不包含查找元素的右边界5即可。我们就创建两个方法，一个方法找左边界另一个找右边界，都用二分查找即可。如果要查找的元素不在nums中，没有左边界就是target在nums的右侧，没有右边界target就在nums的左侧。

查找左边界时，我们要把数组向左侧缩小，当nums[mid] < target时不用管正常继续二分，但是要对nums[mid] >= target这部分进行处理，相当于想让right一直向左收缩，让左边界为right。当nums[mid] = target时，还要向左收缩直到right < left不满足条件时就得到左边界，即为right。如果向左收缩的时候，一直找不到target，就说明没有左边界。

例如nums = [5,7,7,8,8,10]，target = 8。第一次查询为{8,8,10}，此时nums[mid] = 8，再查一次为{10}，

public int leftBorder(int[] nums,int target){
        int leftBorder = -2;
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
                leftBorder = right;
            }
        }

        return leftBorder;
}

右边界也如此，只不过是想让数组向右收缩。

public int rightBorder(int[] nums,int target){
        int rightBorder = -2;
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
                rightBorder = left;
            }
        }

        return rightBorder;
}

27.移除元素

这题既可以暴力又可以双指针，主要来讲双指针就好。双指针法也叫快慢指针法，通过快慢指针以及一个for循环代替两个for循环完成任务。

用双指针法一定要知道两个指针的含义，要不然做的很糊涂，比如这题中，我们要找数组中不是目标数的元素

快指针：就是for循环中的索引，用来遍历数组来找新数组的元素，也就是非目标元素。

慢指针：新数组的索引

比如我通过for循环找到一个非目标数，然后就把他放在慢指针的位置。这就是新数组中的一个元素，之后向后移动快慢指。如果快指针找到一个目标元素，此时慢指针不动，快指针向后移动直到找到非目标元素。

class Solution {
    public int removeElement(int[] nums, int val) {
       //双指针
       int slowIndex = 0;
       int size = nums.length;
       for(int fastIndex = 0;fastIndex < size;fastIndex++){
           if(nums[fastIndex] != val){
               nums[slowIndex] = nums[fastIndex];
               slowIndex++;
           }

       }
       return slowIndex;
    }
}

第一天打卡结束，坚持下来，60天，给自己一个机会