《数据结构与算法》——简单查找

luciferzf

二分查找法：将按大小顺序排列好的数字存放在数组，我们将low，high分别初始化为0和数组下标最大值，mid=(low+high)/2,不断的比较mid指向的元素和待查找元素key的值，若mid>key，则使high=mid，重复之前步骤；反正low=mid，直至key与mid指向元素相等，或low=high。
插值查找：原理与二分查找类似，但是插值查找利用比例来找到mid的下一个位置，即
mid=low+(key-a[low])/(a[high]-key)*(high-low)，来确定下一个mid，进行递归或者迭代。
斐波那契查找：该算法将数组元素不断地分为两个斐波那契数，如大小为13的数组则被分为5和8两个部分，然后比较key与a[5]，以此不断地进行递归或者迭代，直至low=high或找到目标key的下标。当数组元素个数不足时，用最大值补足

#include<cstdio>
#include<cstdlib>
#include<time.h>
#include<iostream>
using namespace std;

class LIST
{
public:
        char name[10];
        int score,ID;
};

int key;


int Input(LIST *&s)
{
        cout << "input the numbers of students；";
        int n;
        cin >> n;
        s = new LIST[n];
        printf("input the student's name,ID numbers,score:\n");
        for (int i = 0; i < n; i++)
        {
                cin >> (s+i)->ID >> (s + i)->name >> (s + i)->score;
        }
        return n;
}

void Binary_search(LIST *s,int low,int high)
{
        int mid = (high + low) / 2;
        int k = (s - mid)->ID;
        if (low == high)
        {
                cout << "no such student" << endl;
                return;
        }
        if (key < (s - mid)->ID)
        {
                cout << (s - mid)->ID << endl;
                Binary_search(s, mid+1, high);
        }
        else if (key > (s - mid)->ID)
        {
                cout << (s - mid)->ID << endl;
                Binary_search(s, low, mid);
        }
        else if (key == (s - mid)->ID)
        {
                cout << "ID:" << (s + mid)->ID << "  name:" << (s + mid)->name << "  score:" << (s + mid)->score << endl;
        }
}

void Inter_search(LIST *s, int low, int high)
{
        int mid = low + (key - (s + low)->ID) / ((s + high)->ID - (s + low)->ID + 1);
        if (low == high)
        {
                cout << "no such student" << endl;
                return;
        }
        if (key > (s + mid)->ID)
        {
                Binary_search(s, mid, high);
        }
        else if (key < (s + mid)->ID)
        {
                Binary_search(s, low, mid);
        }
        else if (key == (s + mid)->ID)
        {
                cout << "ID:" << (s + mid)->ID << "  name:" << (s + mid)->name << "  score:" << (s + mid)->score << endl;
        }
}
int Fabonacci(int n)
{
        int a = 1, b = 1;
        int result = 1;
        while (1)
        {
                if (n > result&&n < a + b)
                {
                        return a ;
                }
                else if(n>a+b)
                {
                        result = a + b;
                        b = a;
                        a = result;
                }
                else if (n == a + b)
                {
                        return result;
                }
                else if (n == result)
                {
                        return b;
                }
        }
}
void Fabonacci_search(LIST *s, int low,int high)
{
        int mid = Fabonacci(high-low)-1;
        //判断是否有不存在的可能
        if (key < (s + mid + low )->ID)
        {
                Fabonacci_search(s, low, mid);
        }
        else if(key > (s + mid + low)->ID)
        {
                Fabonacci_search(s, mid+1, high);
        }
        else if (key == (s + mid + low )->ID)
        {
                cout << "ID:" << (s + mid )->ID << " name:" << (s + mid )->name << " score:" << (s + mid )->score << endl;
        }
}

int main()
{
        LIST *s;
        int n;
        clock_t start,end;
        n=Input(s);
        int choice=1;
        cout << "input the target ID number:";
        cin >> key;
        while (choice)
        {
                printf("1——>二分查找\n2——>差值查找\n3——>斐波那契查找\n0——>结束程序\n");
                printf("input your choice:");
                scanf_s("%d", &choice);
                switch(choice)
                {
                case 1:
                        start = clock();
                        Binary_search(s,0,n);
                        end = clock();
                        cout << "used time is " << (double)(end - start)/ CLOCKS_PER_SEC << endl;
                        break;
                case 2:
                        start = clock();
                        Inter_search(s,0,n);
                        end = clock();
                        cout << "used time is " << (double)(end - start) / CLOCKS_PER_SEC << endl;
                        break;
                case 3:
                        start = clock();
                        Fabonacci_search(s,0,n);
                        end = clock();
                        cout << "used time is " << (double)(end - start) / CLOCKS_PER_SEC << endl;
                        break;
                case 0:
                        break;
                default:
                        cout << "Wrong!"<<endl;
                        break;

                }
        }
        system("PAUSE");
}