704.二分查找

题目：

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

示例：

输入: nums = [-1,0,3,5,9,12], target = 9

输出: 4

解释: 9 出现在 nums 中并且下标为 4

解题思路：

1. 二分法：左闭右闭

二分法使用的前提条件是有序数组和数组中无重复元素，在这道题中两种情况都满足。
左闭右闭区间指的是 [left, right]，初始条件包含了左右两个端点，while 里面的判断条件是 left <= right。
判断区间的时候要注意：

1. 当 nums[middle] > target 时，意味着目标值小于中点值，目标值位于左区间，需要更新右边界，这里的更新规则是 right = middle - 1，因为新的区间不包含中点。
2. 当 nums[middle] < target 时，同样的道理，这里的更新规则是 left = middle + 1。
   代码如下：

var search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    while(right >= left){
        const middle = Math.floor((left+right)/2);
        if(nums[middle] > target){
            right = middle - 1;
        }else if(nums[middle] < target){
            left = middle + 1;
        }else if(nums[middle] == target){
            return middle
        }
    }
    return -1;
};

2. 二分法：左闭右开

更多情况下，会考虑左闭右开区间，这指的是 [left, right)，初始条件包含了左端点为0，右端点为边界+1，while 里面的判断条件是 left < right。
判断区间的时候对于更新右端点的情况，即 nums[middle] > target ，这里会调整成 right = middle，这是因为右端点是开区间，可以在范围内。
代码如下：

var search = function (nums, target) {
    let left = 0;
    let right = nums.length;
    while (right > left) {
        let middle = left + ((right - left) >> 1)
        if (nums[middle] > target) {
            right = middle;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else if (nums[middle] === target) {
            return middle;
        }
    }
    return -1;
};

注意点：

1. 两种方法在取初始端点、判断while条件、循环内取左右端点时遵循 循环不变量 原则，每一次的边界处理都需要按照区间来判断。
2. 取中点的时候一方面可以考虑位运算，>> 1 相当于 ➗ 2，速度会更快，另一方面 left + right 相加可能会数字过大需要处理一下。

27. 移除元素

题目：

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 
给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 
你不需要考虑数组中超出新长度后面的元素。

解题思路：

1. 暴力解法

这种解法只需要两层for循环即可，外层遍历数组元素，内层更新数组，代码如下：

var removeElement = function (nums, val) {
    let size = nums.length;
    for (let i = 0; i < size; i++) {
        if (nums[i] === val) {
            for (let j = i + 1; j < size; j++) {
                nums[j - 1] = nums[j]
            }
            i--;
            size--;
        }
    }
    return size;
};

2. 双指针

这里需要明确的是快慢指针的作用，通过两个指针可以在O(n)的时间复杂度下解决问题。

• 快指针：寻找新数组的元素
• 慢指针：记录新数组的下标位置
  代码如下：

var removeElement = function (nums, val) {
    let slow = 0;
    let fast = 0;
    while (fast < nums.length) {
        if (nums[fast] !== val) {
            nums[slow++] = nums[fast];
        }
        fast++
    }
    return slow;
};

3. 相向双指针法

由于题目不要求顺序保持不变，因此可以让指针从端点开始，左侧寻找和val相同的数，找到后把右侧的值向前挪，然后右侧指针前移，没找到左侧指针后移。
代码如下：

var removeElement = function (nums, val) {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        if (nums[left] === val) {
            nums[left] = nums[right--];
        } else {
            left++;
        }
    }
    return left;
};