您现在的位置是：首页 >其他 >代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素。网站首页其他

704. 二分查找

题目链接：704. 二分查找
我的代码：

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

1. 采用左闭右闭的方式：
   int right = nums.length - 1 和 while (left <= right) 的 “-1”和“<=”要注意。
2. 注意循环语句，是while而不是for。

随想录代码：

class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (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 - 1;
        }
        return -1;
    }
}

1. 补充了target有效判定
2. int mid = left + ((right - left) >> 1) 防止溢出
   int middle = left + ((right - left) / 2)等同于(left + right)/2，但是left + right这个值会很大，可能超过实际的计算机内存。

27. 移除元素

题目链接：27. 移除元素
我的代码：

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left ++;
            }
            else {
                 // right++ 已经包含在循环条件内的了，除了右指针右移，其他不需要操作
            }
        }
        return left;
    }
}

双指针法——思路及算法
由于题目要求删除数组中等于 val 的元素，因此输出数组的长度一定小于等于输入数组的长度，我们可以把输出的数组直接写在输入数组上。可以使用双指针：右指针 right 指向当前将要处理的元素，左指针 left 指向下一个将要赋值的位置。

• 如果右指针指向的元素不等于 val ，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；
• 如果右指针指向的元素等于 val ，它不能在输出数组里，此时左指针不动，右指针右移一位。
  整个过程保持不变的性质是：区间 [0, left ) 中的元素都不等于 val 。当左右指针遍历完输入数组以后， left 的值就是输出数组的长度。即，左指针指向的为新的输出数组（在原数组中的输出数组），返回left就是移除后数组的新长度。
  这样的算法在最坏情况下（输入数组中没有元素等于 val ），左右指针各遍历了数组一次。

与随想录代码一样

1. else语句里没有内容。上层循环默认right是++的，所以不需要else里再操作。