算法之递归、循环、查找

# 1 递归与循环

通常基于递归的代码比较简洁，也比较容易实现，但性能却不如基于循环的实现方法，因为递归时会存在额外的函数调用，内存栈操作以及重复计算，甚至有时会出现调用栈溢出的情况。

但是如果没有特殊要求，可以优先考虑递归的方法写代码。

# 2 查找

顺序查找、二分查找、哈希查找、二叉排序查找都是很基础的内容。

二分查找的灵活运用：在排序数组中查找特定的元素都可以考虑用二分查找来解决，比如查找数字在排序数组中出现的次数（二分查找分别寻找第一个 k 和最后一个 k），比如在排序数组中找出一个值与下标不等/相等的元素等。

# 2.1 二分查找

二分查找法的 O(log n) 让它成为十分高效的算法，主要用于解决在一堆数中找出指定的数这类问题，想要应用二分查找法，这一堆数就必须满足：

• 存储在数组中
• 有序排列

如果数组存储在链表中，就无法使用二分查找了。至于是递增、递减以及是否有重复元素都可以适用，不过通常我们假设数组递增排列，且无重复元素。

下面强烈安利 C++ 标准库 <algorithm> 里简洁无比、bug free 的写法，下面的代码不是原本的实现，但借鉴了其思想。

// 从非递减序列 data 中寻找 value 所在位置
// [first, last) 通常我们习惯了左闭右开的集合表示方法
int BinarySearch(int* data, int first, int last, int value)
{
    while(first < last) // 搜索区间[first, last)不为空
    {
        int mid = first + (last - first) / 2; // 防溢出
        if(data[mid] == value)
            return mid;
        
        if(data[mid] < value)
            first = mid + 1; 
        else
            last = mid;
    }

    return -1;
}

防溢出：防止 (first + last) / 2 溢出，且 mid 为上位中位数（因为写法简洁），由于算中点时应从闭区间一侧向中心靠拢，所以 mid = first + (last - first) / 2，若为 (first, last]，则 mid = last - (last - first) / 2。

二分查找不仅可以用来寻找特定值，也可以用来寻找边界（上界，下界），还可以用上下界来寻找区域。