二分查找和斐波那契查找

Posted on | In , | |
Words count in article: 837 | Reading time ≈ 4

二分查找

复杂度：时间复杂度 O(log2n)，空间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//递归与非递归
#include <iostream>
using namespace std;

int a[] = {1,2,3,4,5,6,7,8};

int BinarySearch1(int l, int r, int value)
{
    int mid = (l + r) / 2;
    if(l == r && a[l] != value)
        return -1;
    if(a[mid] == value)
        return mid;
    if(a[mid] > value)
        return BinarySearch1(l, mid-1, value);
    else
        return BinarySearch1(mid+1, r, value);
}

int BinarySearch2(int value)
{
    int l = 0;
    int r = sizeof(a) / sizeof(a[0]) - 1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(a[mid] == vlaue);
            return (l + r) /2;
        if(a[mid] > value)
            r = mid - 1;
        else
            l = mid + 1;
    }
    return -1;
}

int main()
{
    cout << "Binary Search (recursive) result: " << BinarySearch1(0, sizeof(a) / sizeof(a[0]) - 1, 5) << endl;;
    cout << "Binary Search (no recursive) result: " << BinarySearch2(4) << endl;
}

斐波那契查找

黄金分割：

黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之间，其比值约为1：0.618 或1.618：1

然后我们会发现，随着斐波拉契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。

基本思想：

也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率，同样地，斐波拉契查找也属于一种有序查找算法。

斐波拉契查找与折半查找相似，他是根据斐波拉契序列地特点对有序表进行分割地，他要求开始表中记录地个数为某个斐波拉契数小1，即n = F(k) - 1;

开始将k值与第F(k-1)位置的记录进行比较(即mid = F(k-1) - 1), 比较结果：

  1. 相等
  2. >, low = mid+1, k-=2;

说明：low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。

  1. <，high=mid-1,k-=1。

说明：low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归 的应用斐波那契查找。

复杂度分析：最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <vector>
using namespace std;
const int MAX_SIZE = 20;

int a[] = {1,5,15,22,25,31,39,42,47,49,59,68,88};

void Fibonacci(int F[])
{
    F[0] = 0;
    F[1] = 1;
    for(size_t i = 2; i < MAX_SIZE; i++)
        F[i] = F[i-1] + F[i-2];
}

int FibonacciSearch(int value)
{
    int F[MAX_SIZE];
    Fibonacci(F);
    int n = sizeof(a) / sizeof(int);

    int k = 0;
    while(n > F[k]-1)
        k++;
    vector<int> temp;
    temp.assign(a, a+n);
    for(size_t i = n; i < F[k] - 1; i++)
        temp.push_back(a[n-1]);
    
    int l = 0, r = n - 1;

    while(l <= r)
    {
        int mid = l + F[k-1] - 1;
        if(temp[mid] < value)
        {
            l = mid + 1;
            k = k - 2;
        }
        else if(temp[mid] > value)
        {
            r = mid-1;
            k = k-1;
        }
        else
        {
            if(mid < n)
                return mid;
            else
                return n-1;
        }
    }
    return -1;
}

int main()
{
    int index = FibonacciSearch(88);
    cout << index << endl;
}
Donate? comment?