在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 是数组的长度。

  • 两种算法的主要区别在于分割数组的方式不同,斐波那契搜索使用不等的两部分,而二分搜索使用平均的两部分。这样做的优缺点如下:

    • 斐波那契搜索可以减少访问内存的次数,因为每次只需要计算一个斐波那契数,而不需要除法运算。这在处理大型数据集时可能会有优势。
    • 斐波那契搜索可以更好地适应非均匀访问内存存储的情况,因为它检查相对更接近的元素,在后期可以更快地缩小搜索范围。
    • 二分搜索可以更简单地实现和理解,因为它只需要一次除以二的操作,而不需要额外的斐波那契数列和栈。
    • 二分搜索可以更均匀地利用内存空间,因为它每次都将数组平均分成两半,而不会出现过大或过小的部分。

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status