Junyuan's Homepage

704. 二分查找

题目链接：click here
文章讲解：click here
思路：
这道题是简单的有序二分查找，通过对比当前区间中值和 target 之间的大小关系，来决定移动哪一侧边界。如此循环，直到边界碰撞或找到结果。
细节：
关键在于区间的定义和边界碰撞的条件二者需要配合自洽。
直白来说，就是区间内部是否还有有效值，它可能正好就是最终结果，若不能明确定义，过早退出循环，则会给出target不存在的错误答案。

具体的：
若是左闭右闭区间，则 $left=right$ 时，对应元素 $nums[left] = nums[right]$ ，依旧是有效值，未碰撞。
若是左闭右开区间，则 $left=right$ 时，对应元素 $nums[left] = nums[right]$ ，已经无效值，即碰撞。

所以，前者的退出循环条件为： $left>right$ ，后者为 $left>=right$ 。

代码：

class Solution {
public:
  int search(vector<int> &nums, int target) {
    int index_right = nums.size() - 1;
    int index_left = 0;
    int res = -1;
    if (nums[0] == target) {
      return 0;
    }
    if (nums[index_right] == target) {
      return index_right;
    }

    if (target > nums[index_right] || target < nums[0]) {
      return -1;
    }

    while (index_left <= index_right) {
      int index_mid = index_left + (index_right - index_left) / 2;
      if (nums[index_mid] == target) {
        return index_mid;
      } else if (nums[index_mid] > target) {
        index_right = index_mid - 1;
        continue;
      } else {
        index_left = index_mid + 1;
        continue;
      }
    }
    return -1;
  }
};

27. 移除元素

题目链接：click here
文章讲解：click here

思路：

直觉思路是，暴力双循环遍历，但显然不够。
讲解提示了使用双指针，下面描述自己的想法：

左右指针向中间移动直到碰撞，
nums[left] = target 则停下 left，nums[right] != target 则停下 right，并swap一次。

循环上述过程直到碰撞，即 left >= right，碰撞时元素无需再swap。

直观地说，左指针遇到非 target 就继续右移，遇到 target 需要把它扔到右边，但不是无脑扔，需要找一个位置，这个位置由右指针确定；

右指针遇到 target 就继续左移，遇到非 target 需要等待左指针唤起交换。

这样的过程确保左指针以左的闭区间内都不等于 target，右指针以右的开区间内都等于 target。

最后返回左指针即可。

代码：

class Solution {
public:
int removeElement(vector<int> &nums, int val) {
        int k = 0;
        int left = 0;
        int right = nums.size()-1;
        while (left <= right) {
            while (left <= right  &&  nums[left] != val) {
                left++;
                k++;
            }
            while (left <= right  &&  nums[right] == val) {
                right--;
            }
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
        return k;
    }
};

讲解中的快慢指针法则是从同侧出发，内存覆写的方式完成任务。

快慢指针都从左往右遍历，快指针负责读取数据，而慢指针负责维护自身以左的闭区间内都不等于 target。

快指针读到不等于 target 的数，则记录在慢指针的位置，慢指针自增 1。

快指针读到等于 target 的数，则忽略，继续向前读。

代码：

class Solution {
    public:
    int removeElement(vector<int> &nums, int val) {
            int slow = 0;
            for (int fast = 0; fast < nums.size(); fast++) {
                if (nums[fast] != val) {
                    nums[slow++] = nums[fast];
                }
            }
        }
    };

该方法思路上更加直接，代码逻辑也更简单。

今日收获

个人博客更新。若Blog有误或是有其他想交流的，左侧有联系方式。
复习：
二分查找-区间定义与循环退出条件要自洽，关键是看区间内部是否还有未确定的解
双指针-快慢指针法实现单趟遍历下特定数据的过滤。和给定值相等只是一种特定数据条件
耗时：3h

Junyuan Lu(陆俊元)

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

704. 二分查找

27. 移除元素

今日收获