LeetCode704.二分查找

二分查找是一种基础的算法，其核心思想在高中数学中就已经被大家所熟知了，然而对于代码的实现，其细节问题常常令人头疼，比如while循环的条件是什么？middle是该+1还是-1？这些问题需要有一个清晰的认知。

题目链接如下:704.二分查找
Carl的讲解链接：二分查找

算法思路

二分查找用于从有序序列中搜索某个给定的值

二分查找从序列的中间位置开始搜索，如果中间位置的元素正好就是要找的元素，那么搜索完成；

如果不是，假设该元素小于要找的元素，则在序列的后半部分继续搜索；假设中间的元素大于要找的元素，则在序列的前半部分继续搜索。

并且在缩小的范围中重复使用前面的方法确定范围，直到最终找到元素或者没有元素可供搜索

思考：这样的算法思路是非常直观的，但是在细节方面很容易让人产生疑惑，首先，在数学方法的描述中， middle作为二分的界限，是一个抽象的概念，然而面对一个具体的数组容器，该怎样确定这样的元素？数组长度是奇数或者偶数是否有影响？每一次二分得到的范围是开区间还是闭区间呢？
我觉得完全可以抛弃这样的概念，从二分法的本质来思考问题：首先二分法是一种分治思想的应用，同理，三分法也不是不可以，他们最终的效果是一样的。所以在这样的情形下，只要我们的划分能够满足二分的基本规律，并且能够迭代运行，不断地缩小范围，是不是数学意义上“严格的二分”，或者说每次到底用开区间还是闭区间，middle该不该+1,-1是无关紧要的

所以我们使用一种常见的方法来计算中值：

int middle = (left + right) / 2;

但是在c++中，left + right有溢出的隐患，所以常常改进为：int middle = left + ((right - left) / 2);

同理，使用位运算，也可以得到完全一致的结果：int middle = left + ((right - left) >> 1);

然后，我们就可以使用迭代的方式来开始二分了，假设我们的目标值为int sought,如果sought < middle ,那么 sought一定不在右半边了，所以right = middle；同理，如果 sought > middle，那么sought一定不在左半边了，所以``right = middle`

接下来该如何迭代呢？此时就需要考虑我们的终止条件了：最终找到目标或者没有元素可供继续搜索

根据上面的思路，很容易得出：如果能找到sought那么必然在某一步骤的迭代中产生了middle = sought

如果在某一步的迭代之后区间长度为1，但是此时的 middle != sought，那么显然的，迭代该终止了。同理，如果区间长度最后为0，也就是说通过迭代造成了 left == right,或者说这样的情况下middle再怎么算都会和端点相同，这说明目标不在数组中

对于边界条件的判断是至关重要的，这决定了while循环中的条件该如何安排（不同的实现思路最终体现为“开区间”或者“半开半闭区间的”写法差异），事实上，关于middle+1还是-1的问题恰恰也产生于此：对于迭代终止条件的不同处理方式

我们姑且认为没有找到目标说明数组中left = right，以下是一种想当然(没有批评的意思)的代码实现:

class Solution {
public:
    int search(vector<int>& nums, int sought) {
        int left = 0;
        int right = nums.size();
        while (left < right) { 
            int middle = left + ((right - left)/2);
            if (nums[middle] > sought) {
                right = middle; 
            } else if (nums[middle] < sought) {
                left = middle;
            } else { 
                return middle; 
            }
        }
        // 未找到目标值
        return -1;
    }

这种情况下，如果sought在vector nums 之中，代码是可以正确运行的，然而如果sought不在nums中，最终二分导致left和right相邻，此时middle再次迭代会仍然等于left，我们认为sought在left与right之间，但实际上已经不能再二分，所以程序在这里会陷入死循环。

为了解决在这样的问题，我们知道，实际上如果middle的值在二分的某一步，是不等于sought的，那么实际上下次二分的数组范围内就应该排除middle，用这样的方式，在最后的迭代中就不会出现问题了。
以下是Carl的代码：

class Solution {
public:
    int search(vector<int>& nums, int target
        int left = 0;
        int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间，在[left, middle)中
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，在[middle + 1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

处理以下while循环的条件，就可以得出另一种写法了：（还是Carl教程里的）

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

额外的思考

二分的思路是非常清晰的，仿佛对于开区间闭区间还有left = middle + 1或者 right = middle-1的疑惑，就像初学者面对for循环中i <= n和i < n一样。

究竟该如何考虑这样的问题呢？我想对于解决问题而言，首先需要有自己熟悉的一套写法，或者是模板，然后才需要对为什么这样写有一个认知。二分法的写法非常多，是否能够举一隅反三隅，就看能不能明白这些操作的底层原理。

对于边界的疑惑，对循环条件的疑惑，其实都和最后的终止条件关系密切，设想以下最后长度为3，2，以及1的数组，看看自己的代码在这样的情况下会如何执行，稍稍debug以下就明白其中的逻辑了。同时如果对这样的内容感到繁琐和困惑，也不一定需要投入大量的时间来强迫自己熟悉这样的流程。

毕竟我们都知道：Keep it simple and stupid.
用这样的解决方式，我们有更加通用的解答方式：使用迭代器实现二分查找，这里的left和right我们分别由beg和end代替。代码如下：

auto beg = nums.begin(), end = nums.end();
auto mid = nums.begin() + (end - beg)/2;


while (mid != end && *mid != sought){ 
    if(sought < *mid){
        end = mid;
    }
    else{
        beg = mid + 1;
    }
    mid = beg + (end - beg)/2;
}

LeetCode27.移除元素

这道题的主流解决方案是一个双指针（快慢指针的内容）
Carl的动画讲解非常直观，链接如下：27.移除元素
题目链接：LeetCode27.移除元素

题目中对于双指针的应用是非常直观的，我看了讲解和示例代码就能自己写出来了。我不太想在这道题上花时间，这种思路的深入理解，等我到遇到更多的同类型的问题再考虑吧。
代码如下，一次AC：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) { //val is the element supposed to be deleted.
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};

也许快慢指针从名字听起来不是很直观，也许认为“快指针”用来遍历每一个元素，“满指针”定位覆盖存储的位置，是不是会更清晰一些？