【查找算法】基于比较的查找算法（顺序查找、对分查找、分块查找）

1、顺序查找：O(n)

//1、顺序查找
int SequentialSearch(int *array, int n, int key)
{
    int i=0;
    while( i < n  &&  array[i] != key)
    {
        ++i;
    }
    if (array[i] == key)
    {
        cout<<"Find: ";
        cout<<i;
        return i;
    }
    else 
    {
        cout<<"Not Find!";
        return -1;
    }
}

int SequentialSearchAdvanced(int *array, int n, int key)
{
    int i=0;
    while(array[i] != key)
    {
        ++i;
    }
    if (i < n)
    {
        cout<<"Find: ";
        cout<<i;
        return i;
    }
    else 
    {
        cout<<"Not Find!";
        return -1;
    }
}

2、对分查找：

前提：从小到大有序排列

时间复杂度：O(log₂n)

//2、对分查找
int BinarySearch(int *array, int n, int key)
{
    int left=0, right=n-1, mid;
    while (left<=right)
    {
        mid = (left+right)/2;
        if (key < array[mid])
        {
            right = mid-1;
        } 
        else if( key > array[mid])
        {
            left = mid+1;
        }
        else
        {
            cout<<"Successful Search!"<<endl;
            cout<<mid<<endl;
            return mid;
        }
    }
    cout<<"Search failure!"<<endl;
    return -1;

}

3、分块查找：又称索引顺序查找，这是顺序查找的一种改进方法，用于在分块有序表中进行查找 。

主表：存储数据的表，长度n；

索引表：将主表分块，每块长s，找出每块中的关键字最大值，并且保存该块中所有数据在主表中的索引

（1）分块：将n个数据元素“按块有序”划分为m块。

每一块中的结点不必有序，但块与块之间必须“按块有序”；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素。每个块中元素不一定是有序的。

（2）根据查找值，和索引表中关键字（每块中的最大关键字）比较，通过对分查找/顺序查找，找到该值所在的块范围；

（3）在相应块中，找到该值在主表中的位置。

平均查找长度ASL<=O(log₂(n/s))+s/2  （先对分查找，或顺序查找）

//3、分块查找
//索引表：key记录每块的最大关键值，link记录该块数据在主表中的起始位置
//建立4个块
struct index
{
    int key;
    int link;
}indexChart[4];

//array:主表  n：主表长度  indexChart：索引表  BlockNumber:块个数  key：要查找的关键字
int IndexSearch(int *array, int n, index indexChart[], int BlockNumber, int key)
{
    int indexNumber = 0;
    int BlockStart = 0, BlockEnd = 0;
    //查找所在块
    while(indexNumber<BlockNumber  &&  key>indexChart[indexNumber].key)
    {
        ++indexNumber;
    }
    if (indexNumber >= BlockNumber)
    {
        cout<<"Search failure!"<<endl;
        return -1;
    }
    //查找所在主表位置
    else
    {
        BlockStart = indexChart[indexNumber].link;
        if (BlockStart == BlockNumber-1) 
        {
            BlockEnd = n;
        }
        else
        {
            BlockEnd = indexChart[indexNumber+1].link -1;
        }
        int j = BlockStart;
        while(key != array[j] && j<=BlockEnd)
        {
            ++j;
        }
        if (key == array[j])
        {
            cout<<"Successful Search!"<<endl;
            cout<<j<<endl;
            return j;
        }
        else
        {
            cout<<"Search failure!"<<endl;
            return -1;
        }
    }
}
void IndexSearchSample()
{
    int a[] = {1,2,5,6,7,8,9,10,11,12,13,14,15,16,17,18};
    for (int i=0; i<4; i++)
    {
        indexChart[i].link = i*4;
        indexChart[i].key = a[i*4+3];        
    }
    int i = IndexSearch(a,16,indexChart,4,13);
}