1 二分法

704 二分查找

题目：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4     

输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1     

前提：1. 有序数组 2. 无重复元素

要点

1. 循环不变量
   a. while(left < right) or while(left <= right)
   b. right = middle or right = middle - 1
   其实这两者对应的是 [left, right) 左闭右开区间或者 [left, right] 左闭右闭区间。个人习惯是写左闭右开，即 left < right 和 right = middle。左闭右开，对应初始化 left = 0; right = nums.size()，right 是取不到的，所以 left 不会等于 right，且 right 应更新为 middle。
   此外注意当 target > middle 的时候，left 应更新为 middle + 1，这是因为 middle 已经不应在搜索范围。
2. 中点的取法
   使用 left + (right - left) >> 1 是为了避免计算 left + right 的时候 overflow，>> 1 右移一位的运算相当于除以2。
3. 易错注意 位运算的优先级，需要加括号。

代码

时间复杂度 O(N) 空间复杂度 O(1)

左闭右开

C++

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

Python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)
        while left < right:
            middle = left + ((right - left) >> 1)
            if target < nums[middle]:
                right = middle
            elif target > nums[middle]:
                left = middle + 1
            else:
                return middle
        return -1

左闭右闭

C++

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

2 双指针

27 移除元素

题目：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
*你不需要考虑数组中超出新长度后面的元素。

要点

1. 暴力解法 千万注意size--的同时 i--，这是因为去掉一个值后的数组 index 也会左移一位。
2. 双指针即使用一层循环做双层循环的事。注意确定什么时候动左指针，什么时候动右指针的条件。
3. 同向双指针。对快指针遍历，当遇到与 val 不同的值的时候慢指针才会移动，否则快指针遇到等于 val 的值，不应被保留，快指针不动，nums[i] 不更新。

代码

暴力双循环法

先在外层遍历i，当 nums[i] = val 的时候，j 从 i+1 开始遍历到小于 nums.size()，并赋值 nums[j-1] = nums[j]（这里要注意循环不变量的问题）。
时间复杂度 O(N^2) 空间复杂度 O(1)
C++

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // O(N^2)
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) {
                for (int j = i + 1; j < size; j++) {
                    nums[j-1] = nums[j];
                }
                i--;
                size--;
            }
        }
        return size;
    }
};

双指针法

1. 快慢指针、同向双指针
   时间复杂度 O(N) 空间复杂度 O(1)
   C++

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // O(N)
        int size = nums.size();
        int i = 0;
        for (int j = 0; j < size; j++) {
            if (val != nums[j]) { // when j not equal to val
                nums[i++] = nums[j];
            }
        }
        return i;
    }
};

2. 相向双指针
   时间复杂度 O(N) 空间复杂度 O(1)
   有些难以理解。先保留在这。