查找一之顺序查找、二分查找、分块查找

1、概念：在一些有序的或无序的数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程叫做查找，也就是给定一个值，在查找表中确定一个关键字等于给定值的记录或数据元素。

2、平均查找长度（后期可能会增加）

3、查找长度分为成功和失败两种

4、顺序查找

　　1、主要思想：将查找值顺序逐个与结点值进行比较，相等即为查找成功，否则查找失败

　　2、代码实现

int SqSearch(int a[],int len,int e)
{
    int i = 0;
    while(i < len && a[i]!= e)
    {
        i++;
    }
    if(i >= len)
    {
        return 0;//没有找到
    }
    return i+1;//返回逻辑序号
}
//时间复杂度：O(n)
//查找成功平均长度 （n+1）/ 2
//查找失败平均长度 n / 2

5、二分查找（折半查找）

　　1、算法思想：每次比较中间值和待查找值得大小，然后更新范围，最后确定具体位置（重点：序列有序）

　　2、代码实现

int BinSearch(int a[],int len,int e)
{
    int i = 0;
    int j = len-1;
    int mid;
    while(i <= j)
    {
        mid = j/2;
        if(e > a[mid])
        {
            i = mid +1;
        }
        else if(e < a[mid])
        {
            j = mid-1;
        }
        else return mid+1;

    }

    return -1;

}
//时间复杂度：log2n
//ASL成功：1/n累加（times*deepth）
//ASL失败：1/n累加（fails*deepth）
//以二叉树了理解，排序写完会重新更新这一块内容

6、分块查找

　　1、算法思想：

　　　　1、把表长为n的线性表分成m块，前m-1块记录个数为 t = n / m t=n/m t=n/m，第m块的记录个数小于等于t；

　　　　2、块间有序，块中无序

　　　　3、建立索引表，其中记录每个块的起始位置以及最大元素

　　　　4、在增加元素的时候，根据索引表就知道在哪一块，把数据加到相应的块就好，因为块内无序；在查找时，索引表过大可以使用二分查找，会找到块在顺序查找，可能不会比二分查找好，但是不需要数据完全有序

　　2、代码1

typedef struct
{
    int key;
    int link;
}IdxType;

int IdxSearch(IdxType I[],int b,int a[],int len ,int k)//b是分的块数，a是原数组，I是索引表，len是a数组的长度，k是需要查找值
{
    int s;
    int l;
    int r;
    int mid;
    s = (len+b-1)/b;//注意啊，确实是向下取整，
    l = 0;
    r = b-1;
    int i;
    while(l <= r)//对索引表进行二分查找
    {
        mid  = l+(r-l)/2;
        if(I[mid].key >= k)
        {
            r = mid -1;
        }
        else
        {
            l = mid +1;
        }
    }
    i = I[r + 1].link;
    while(i <= I[r+1].link + s -1 && a[i] !=k)//块内顺序查找
    {
        ++i;
    }
    if(i <= I[r+1].link +s -1)
    {
        return i+1;//索引值没有越界的时候，就返回他的逻辑位置
    }
    return -1;

}

　　3、代码2

#include<stdio.h>

struct indexBlock//定义块的结构
{
    int key;
    int start;
    int end;
}indexBlock[4];

int search(int key,int a[]);

int main()
{
    int i;
    int j = -1;
    int k;
    int key;
    int a[] = {12,25,33,36,57,146,219,254,315,336,358,795,876,951,999};
    printf("已知有一组数：\n");
    for(i = 0;i < 15;i++)
    {
        printf("%d ",a[i]);
        if((i+1)%5==0 && i < 14)
        {
            printf("|");
        }
    }
    printf("\n");

    //确定模块起始值和最大值
    for(i = 0;i < 3;i++)
    {
        indexBlock[i].start = j+1;
        j++;
        indexBlock[i].end = j+4;
        j += 4;
        indexBlock[i].key = a[j];//确定每一块的最大值？//直接赋值因为数组初始化的时候块的最后一个值最大值，违背了块内无序啊

        printf("indexBlock[%d].start = %d\n",i,indexBlock[i].start);
        printf("indexBlock[%d].end = %d\n",i,indexBlock[i].end);
        printf("indexBlock[%d].key= %d\n",i,indexBlock[i].key);
    }

    //
    printf("input the num you want to search:");
    scanf("%d",&key);
    k = search(key,a);

    //
    if(k > 0)
    {
        printf("Find,Location is %d\n",k+1);
    }
    else
    {
        printf("Search Fail!\n");
    }
    return 0;

}

int search(int key,int a[])
{
    int i,startvalue;
    i = 0;
    while(i < 3 && key > indexBlock[i].key)
    {
        i++;
    }
    if(i >= 3)
    {
        return -1;
    }
    startvalue = indexBlock[i].start;

    while(startvalue <= indexBlock[i].end && a[startvalue] != key)
    {
        startvalue++;
    }
    if(startvalue > indexBlock[i].end)
    {
        startvalue = -1;
    }
    
    return startvalue;
}