琐碎简记

注：本篇使用语言：C++

基本背景与类似情况

二分查找原理本身很简单：对一顺序数组取中间值，比较其与目标大小，让中间值成为新边界，二分缩短区间。此过程迭代进行，直到找到或找不到目标，时间复杂度$O(logn)$

典型的类似情况是快排，因为二者本质上都是在选取中间值并更新边界的过程。

具体分析与处理

对中间索引的微处理

理想状态而言应该是一直选取到中间，然后更新：比如在目标值大于中间值时，更新左边界为中间本身，右边界不变。如此往复直到夹逼出一个数

但索引本身是离散的，这导致的问题是数学算式mid=(left+right)/2可能出现索引mid是浮点数的情况，毕竟卡到两数中间时无法取值。而代码中mid的唯一写法也只能是mid=(left+right)/2（一个等效写法是(right-left)/2+left，二者完全相同，不展开），这会导致mid其实既可能是正中间，也可能是中间稍左的位置。

注：两种算中点的方式还真不同：前者先算left+right是有溢出风险的…还是后者好些

如果递归函数传参时直接将mid本身传进去，就会导致在只剩两个数时无法继续更新的情况（mid会一直与左边界相等）。而递归函数一般来说做特判都是逻辑对全过程不统一然后出bug的前兆，故应该意识到理论和实际是有差距的，需要具体情况进行微调。

解决方法是利用离散本身的特点：“mid需要成为下一次递归的边界”本身已经暗示了一个事实：其对应的数已经被判断过了。在连续情况下这代表着mid是一个开区间而非闭区间，但因为其对应的位置本身不变而有被忽视的可能，但在这里，开闭直接决定了了传入的是mid±1还是其本身。

也就是说，原来的方法的错误原因是，每次递归都会进行一次多余的比较，而该次比较是能对是否继续递归产生影响的。也就是说，还是逻辑没有捋清楚导致的。

对终止判断的选取

如果能考虑到mid更新时需要手动±1，这里会好想到些，不过或许还是积累记住更为重要？

递归函数的终止是难点。除去比较好理解的因为达到目的而结束递归，另一种对无法达成目的的判断更不好想到（比如这里可能目标根本不在数组里）

考虑到二分缩减区间的直观解释，无法达成显然代表着即使区间缩完也没有找到。而区间缩完也就代表着左边界等于右边界。

这是必然能达成的吗？由于mid的最小移动量（相对于左边界）是0（靠奇数除2后舍去小数），而每次mid只会取代一个边界，另一方不变，而更新边界时数量上只有1的变化，故应该是能做到相等的。

但用相等判据需要判断两条：左右边界相等且该点值不为目标值。事实上有更自然的方法：当左边界大于右边界时结束。这是依靠了mid每次必然±1的特性（没法解释了，属于是初见会抱怨为什么想不到，但如果不看就真的想不到的判据）

最终代码 

class Solution {
public:
    int solve(vector<int>&nums,int target,int left_edge,int right_edge){
        int mid = (left_edge+right_edge)/2;
        if(nums[mid]==target){
            return mid;
        }
        else if(left_edge>right_edge){
            return -1;
        }
        if(nums[mid]>target){
            return solve(nums,target,left_edge,mid-1);
        }
        else{
            return solve(nums,target,mid+1,right_edge);
        }
    }
    int search(vector<int>& nums, int target) {
        int left_edge = 0;
        int right_edge = nums.size()-1;
        int ans = solve(nums,target,left_edge,right_edge);
        return ans;
    }
};

拓展：关于Wrapper Function

在LeetCode中，已经给出了测试函数：

class Solution {
public:
    int search(vector<int>& nums, int target) {
      //Coding here
    }
};

实际上也有很多为了接口设计或类似原因，提供进来的接口不能随便改的情况。显然这个函数本身不适合设计为递归函数（先不考虑循环，二者原理本质一样的）。

这种情景下常设计一个Wrapper Function，它的传参等情况专门为解决问题而设计。让接口传入后准备递归入口需要的数据，然后让入口函数本身来调用递归函数就行了。具体如：

class Solution {
public:
    int solve(int data);//具体实现略
    int search(vector<int>& nums, int target) {
      int data = nums.size();
      int ans = solve(data);
      return ans;
    }
};

这也能保证专门用来解决问题的函数的内部处理时用的变量不泄露到区域外去，算是一种好习惯吧。

说些什么吧！

waline