顺序表和线性索引查找

顺序表查找

查找（Searching）就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。
查找表（Search Table）是由同一类型的数据元素（或记录）构成的集合。
关键字（key）是数据元素中某个数据项的值。
若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（Primary Key）
对于可以识别多个数据元素（或记录）的关键字，称为次关键字（Secondary Key）
查找表按照操作方式分为：静态查找表和动态查找表
静态查找表（Static Search Table）：只作查找操作的查找表，主要操作如下：
（1）查询某个“特定的”数据元素是否在查找表中
（2）检索某个“特定的”数据元素和各种属性
动态查找表（Dynamic Search Table）：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。
（1）查找时插入数据元素
（2）查找时删除数据元素
为了提高查找效率，我们需要专门为查找操作设置数据结构，这种面向查找操作的数据结构称为查找结构。

1.顺序查找（Sequential Search）又叫做线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值
比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不相等时，则表中没有
所查的记录，查找不成功。
优点：算法简单，逻辑次序无要求，且不同存储结构均适用
缺点：ASL（平均查找长度），时间效率太低
2.折半查找（二分查找）----递归：在原数据有序的情况下，每次将待查记录所在区间缩小一半
3.插值查找：根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心在于插值公式 s=(key-a[low])/a[high]-a[low]
折半查找：mid=(low+high)÷2=low+(high-low)÷2;插值查找mid=low+s×(high-low)，该方法适用于对于表长较大，关键字分布比较均匀的查找表
4.斐波那契查找：根据黄金分割原理实现，如果要查找的记录在右侧，则左侧的数据就不用再判断了
代码示例：
SSearch.h

#pragma once

//顺序查找
int Sequential_Search(int* a, int n, int key);

//每次循环都需要判断i是否越界，故可以设置一个哨兵a[0]=key，每次都不会与n比较了,查找失败返回0
//顺序查找优化
int Sequential_Search2(int* a, int n, int key);

//折半查找（二分查找）：在原数据有序的情况下，每次将待查记录所在区间缩小一半
int Binary_Search(int* a, int n, int key);


//折半查找（二分查找）----递归：在原数据有序的情况下，每次将待查记录所在区间缩小一半
//优点：效率比顺序查找高
//缺点：只适用于有序表，且限于顺序存储结构（对线性链表无效---找不到中间位置）-----适用于静态查找表
int Binary_Search2(int* a, int key, int low, int high);

//插值查找：根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心在于插值公式  s=(key-a[low])/a[high]-a[low]
//折半查找：mid=(low+high)/2=low+(high-low)/2;插值查找mid=low+s*(high-low)，该方法适用于对于表长较大，关键字分布比较均匀的查找表
int Insert_Search(int* a, int n, int key);

//斐波那契查找O(log n)，也需要有序
int Fibonacci_Search(int* a, int n, int key);
*/

SSearch.cpp

#include "SSearch.h"

//顺序查找
int Sequential_Search(int* a, int n, int key)
{
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == key)
        {
            return i;
        }
    }
    return 0;
}

//顺序查找优化
int Sequential_Search2(int* a, int n, int key)
{
    int i = n;
    a[0] = key;
    for (; a[i] != key; i--);

    return i;
}

//折半查找（二分查找）：每次将待查记录所在区间缩小一半
int Binary_Search(int* a, int n, int key)
{
    int low = 1, high = n;
    int mid;
    while (high >= low)
    {
        mid = (low + high) / 2;
        if (a[mid] == key)
        {
            return mid;
        }
        else if (a[mid] > key)
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }

    return 0;
}

//
//折半查找（二分查找）----递归：在原数据有序的情况下，每次将待查记录所在区间缩小一半
int Binary_Search2(int* a, int key, int low, int high)
{
    int mid = (low + high) / 2;

    if (high < low)
    {
        return 0;
    }
    if (a[mid] == key)
    {
        return mid;
    }
    else if (a[mid] > key)
    {
        return Binary_Search2(a, key, low, mid - 1);
    }
    else
    {
        return Binary_Search2(a, key, mid + 1, high);

    }

}

//插值查找
int Insert_Search(int* a, int n, int key)
{
    int low = 1, high = n;
    int mid;
    while (high >= low)
    {
        mid = low + (key - a[low]) / (a[high] - a[low]) * (high - low);

        if (a[mid] == key)
        {
            return mid;
        }
        else if (a[mid] > key)
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }

    }

    return 0;
}

//斐波那契查找
//int a6[9] = { 0,1,2,5,5,6,7,7,8 };            //第一个位置空出来

int Fibonacci_Search(int* a, int n, int key)    //key=6,n=8
{

    //斐波那契数列
    int F[10] = { 0,1,1,2,3,5,8,13,21,34 };
    int low = 1, high = n, mid, k = 0;
    while (n > F[k - 1])
    {
        k++;                                //找到n位于斐波那契数列中的位置6
    }

    for (int i = n; i < F[k] - 1; i++)      //F[6]=8
    {
        a[i] = a[n];
    }

    while (low <= high)
    {
        mid = low + F[k - 1] - 1;
        if (key < a[mid])
        {
            high = mid - 1;
            k = k - 1;
        }
        else if (key > a[mid])
        {
            low = mid + 1;
            k = k - 2;
        }
        else
        {
            if (mid <= n)
            {
                return mid;
            }
            else
            {
                return n;
            }
        }
    }

    return 0;
}

main.cpp:

#include <iostream>

#include "SSearch.h"

using namespace std;

int main(int argc, char** argv)
{
    int a[9] = { 0,1,34,5,5,6,7,7,8 };          //第一个位置空出来
    int index = Sequential_Search(a, 8, 6);
    cout << "index=" << index << endl;

    int a2[9] = { 0, 1,34,5,5,6,7,7,8 };        //第一个位置作为哨兵
    int index2 = Sequential_Search2(a2, 8, 6);
    cout << "index2=" << index2 << endl;

    int a3[9] = { 0,2,5,14,54,65,465,3455,34535 };
    int index3 = Binary_Search(a3, 8, 65);
    cout << "index3=" << index3 << endl;

    int index4 = Binary_Search2(a3, 65, 1, 8);
    cout << "index4=" << index4 << endl;

    int index5 = Insert_Search(a3, 8, 65);
    cout << "index5=" << index5 << endl;

    int a6[14] = { 0,1,2,5,5,6,7,7,8 ,0,0,0,0,0 };          //第一个位置空出来
    int index6 = Fibonacci_Search(a6, 8, 6);
    cout << "index6=" << index6 << endl;

    return 0;
}

线性索引查找

线性索引查找，索引就是把一个关键字与它对应的记录相关联的过程，线性索引就是将索引项集合组织为线性结构，也称为索引表
1.稠密索引：在线性索引中，将数据集中的每个记录对应一个索引项，索引项按照关键码有序排列。索引项有序就意味着我们查找关键字时可以用到折半、插值、斐波那契等有序查找算法
2.分块索引：
稠密索引因为索引项与数据集的记录个数相同，所以空间代价很大。为了减少索引项的个数，可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引项的个数。
分块有序，是把数据集的记录分成了若干块，并且这些块需要满足两个条件：
（1）块内无序，即每一块内的记录不要求有序，当然如果能让块内有序更理想，不过要付出很大的时间和空间代价。
（2）块间有序，要求第二块所有记录的关键字均要大于第一块中所有记录的关键字，第三块的所有记录的关键字均要大于第二块的所有记录关键字，因为块间有序，才有可能在查找时带来效率。
对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引。分块索引的索引项结构分为三个数据项：
（1）最大关键码，存储每一块中的最大关键字，使得在它之后的下一块中的最小关键字也能比这一块最大的关键字大
（2）存储了块中的记录个数，以便于循环时使用。
（3）指向块首数据元素的指针，便于开始对这一块中记录进行遍历。
步骤：
（1）在分块索引表中查找要查关键字所在的块，由于块间有序，可以利用折半、插值等算法得到结果。
（2）根据块首指针找到相应的块，并在块中顺序查找关键码，因为块中可以是无序的，需要顺序查找。
3.倒排索引：：倒排索引的索引项的通用结构是：
次关键码
记录号表，存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字）
索引源于实际应用中需要根据属性（或者字段、次关键码）的值来查找记录，这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。
由于不是由记录来确定属性值，而是由属性值确定记录的位置，因而称为倒排索引。