Binary Search & Fibonacci Search

2023 年 09 月 23 日

494 次浏览

1436字数

在Binary Search时，

```
while(l <= r) {
    if (check(mid) < target) l = mid + 1;
    else if (check(mid) > target) r = mid - 1;
    else return mid; 
}
```

实际上，如果我们使用递归树来模拟这一迭代过程，我们可以发现，在相同递归层数的情况下，靠右的递归栈的总操作次数大于左边，导致一个不平衡的查找效率。因此，我们使用 Fibonacci 数列进行黄金分割来消除这种不平衡。

```
class Solution {
public: 
    stack <int> fib;
    int low = 0, upp = 1;
    int search(vector<int>& nums, int target) {
        fib.push(low), fib.push(upp);
        while(low + upp < nums.size()) {
            fib.push(low + upp);
            low = upp, upp = fib.top();
        }
        int l = 0, r = nums.size() - 1;
        while(l <= r) {
            while(!fib.empty() && fib.top() > r - l + 1) fib.pop();
            int mid = l + fib.top() - 1;
            if (nums[mid] < target) l = mid + 1;
            else if (nums[mid] > target) r = mid - 1;
            else return mid;
        }
        return -1;
    }
};
```

* 斐波那契搜索（Fibonacci Search）:
  利用斐波那契数列来分割数组，每次比较数组中的第 F(m-2) 个元素和目标元素，其中 F(m) 是大于或等于数组长度的最小斐波那契数。如果相等，则返回索引；如果小于，则在右边的 F(m-1) 个元素中继续查找；如果大于，则在左边的 F(m-2) 个元素中继续查找。这种算法的时间复杂度是 O(1.44 \* log n)，其中 n 是数组的长度。
* 二分搜索（Binary Search）:
  每次将数组分成两个相等的部分，比较中间元素和目标元素。如果相等，则返回索引；如果小于，则在右半部分继续查找；如果大于，则在左半部分继续查找。这种算法的时间复杂度是 O(1.50 \* log n)，其中 n 是数组的长度。
* 两种算法的主要区别在于分割数组的方式不同，斐波那契搜索使用不等的两部分，而二分搜索使用平均的两部分。这样做的优缺点如下：
  * 斐波那契搜索可以减少访问内存的次数，因为每次只需要计算一个斐波那契数，而不需要除法运算。这在处理大型数据集时可能会有优势。
  * 斐波那契搜索可以更好地适应非均匀访问内存存储的情况，因为它检查相对更接近的元素，在后期可以更快地缩小搜索范围。
  * 二分搜索可以更简单地实现和理解，因为它只需要一次除以二的操作，而不需要额外的斐波那契数列和栈。
  * 二分搜索可以更均匀地利用内存空间，因为它每次都将数组平均分成两半，而不会出现过大或过小的部分。

最后修改：2023 年 09 月 23 日