LeetCode 704 二分查找

题目链接：https://leetcode.cn/problems/binary-search/

自己遇到的问题：

1、在LeetCode执行代码时报错

error: cannot find symbol [in __Driver__.java]
      double[] ret = new Solution().dicesProbability(param_1);
                                   ^
  symbol:   method dicesProbability(int)
  location: class Solution

原因是我更改了原来LeetCode 上函数的名字所以报错。

代码实现

这里是左闭右闭的写法 [left,right] 的代码实现

public static  int Search(int[] nums,int target){
        if(target < nums[0]|| target > nums[nums.length-1])//先判断是否符合要求，因为数组是有序的
            return -1;
        int left = 0,right = nums.length - 1;
        while(left <= right){//左闭右闭的含义是一个数值能否同时等于left和right
            int mid =  (left+ right)/2;
            if(nums[mid] == target){
                return mid;
            }else if(target > nums[mid]){
                left = mid + 1;//如果target在右边，则进右区间
            }else if(target < nums[mid]){
                right = mid - 1;//在左边更改右边界，进 左区间
            }
        }
        return -1;
    }

这里是左闭右开的写法[left,right) 代码实现

public int search(int[] nums, int target) {
        int left = 0, right = nums.length;//这里不需要减一，因为取不到，右开。
        while (left < right) {//left right不能相等
            int mid = left + ((right - left) >> 1);//取中
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;//对于左边界可以取到
            else if (nums[mid] > target)
                right = mid;//右边界取不到
        }
        return -1;
    }

总结

二分查找算法的重难点我认为就是定义区间的端点，一般有两种情况一种就是左闭右闭一种则是左闭右开。

1、在左闭右闭的情况下，我们每次都要扫描区间的两个端点，所以在这种情况下如果中间元素大于Target或者中间元素小于Target，那么我们对应的需要更新mid左边一个或者mid右边一个的位置。
2、在左闭右闭的情况下，我们每次都要扫描区间的左端点left，但是不扫描right，因此我们使用中间元素去比较目标值Target的时候，如果中间值大于Target，此时我们应当更新左区间的右端点，但是又因为我们不扫描右端点所以此时更新right的时候，直接等于right = mid即可，如果中间值小于Target，则更新left = mid+1。

LeetCode 27 删除元素

题目链接：https://leetcode.cn/problems/remove-element/

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针

快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
慢指针：指向更新 新数组下标的位置

代码实现

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

总结

这里的快指针在不停的进行for循环，然后向前走，看到不等于val的才将值赋值给慢指针