警惕无限递归

二分

  今天在做二分类型题时，再次遇到了令人恶心的“特殊情况”引发的无限递归，因此写此文章警示自己。
对于数组 [2, 1, 3, 4, 5]
当我将其通过如下方式二分时：

int quick_sort(int l, int r)
{
    if (l >= r) return a[l];
    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    while (i < j){
        do i ++; while(a[i] < x);
        do j --; while(a[j] > x);

        if (i < j) swap(a[i], a[j]);
    }

    if (j > k) return quick_sort(l, j - 1);
    else return quick_sort(j, r);
}

将容易出现无限递归的情况；如：
递归后 (k = 3)
（1） j = 3， 数组 [3, 4, 5]
（2） j = 3， 数组 [3, 4, 5]
（3） j = ……， 代码将无休止的运行

正确代码：

// 改变判断条件（原因等我学过二分了再详细讨论）
if (j >= k) return quick_sort(l, j);
else return quick_sort(j + 1, r);

同样的， 可以对二分代码进行改进

if (i < j) 
{
	swap(a[i], a[j]);
    i ++, j --;
}
// 这样递归结束后也不会出现无限递归的问题