静态查找（二分查找）_静态查找表的操作实验-二分查找

静态查找：顺序查找 折半查找（二分查找） 分块查找

 

顺序查找

平均查找长度ASL

对于含有几个记录的表，查找成功时的平均查找长度为 

Pi为查找表中第i个记录的概率，(等概率1/n)

Ci为找到第i个元素，需要比较的次数

顺序查找

优点：既适用于线性表的顺率存储，又适用于链式存储。

设置监视哨的顺序查找

通过设置监视哨，免去查找过程中每一步都要检测整个表是查找完毕

原本的方法：比较两次:是否直找完整个表，是否找到 (==)

 ST.R[0].key=key;
 for(i=ST.length;ST.R[i].key!=key;i--);//循环体为空语句！！！
 return i;

 

把“要查找”的元素设置为：“监视哨”

所以但凡对比到：“监视哨”，就是其它全部对比完了，没有找到→return 0;

for循环的循环体是：空语句

(for循环一定有循杯体)

循环条件：ST.R[i].key!=key 

满足循环条件，继续进行

即不是要查找的元素就继续进行

(没找到继续找)

如果找到，跳出循环，此时的i–>位置值就是要查找的元素的位置

跳出循环之后，才执行return语句.

return i:找到–>正常位置 –>位置值

未找到 –>范围外的位置 ~

·查找是：从后往前，还是从前往后，这个看自己需要，考虑时间，空间复杂度。

#include<iostream>
using namespace std;
 
typedef int Status;
#define  OK 1
#define ERROR 0
#define OVERFLOW -1
 
//typedef int ElemType;
typedef int KeyType; 
typedef int InfoType; 
 
 
typedef struct
{
    KeyType key;
    InfoType otherinfo;
}ElemType;
 
 
typedef struct
{
    ElemType* R;
    int length;
}SSTable;
 
//顺序查找
int Search_Seq(SSTable ST,KeyType key)
{
    for(int i=ST.length;i>=1;i--)
    {
        if(ST.R[i].key==key)  return i;
    }
    return 0;
}
 
//设置监视哨的顺序查找
int Search_Seq(SSTable ST,KeyType key)
{
    int i;
    
    ST.R[0].key=key;
    for(i=ST.length;ST.R[i].key!=key;i--);//循环体为空语句！！！
    return i;
 
}
 
int main()
{
 
    return 0;
}

折半查找.(二分查找)

前提要求：必须采用顺序存储结构，必须是有序表

每一次的查找，都是对比mid.位置处的元素mid为中间位置，low表示区间下界，high表示区间下界

每次查找对比失败，改变的都是“查找区间” 直到 查找.最终失败或查找成功

改变：查找区间”， 留下部分，摘除部分

由high和low确定区间（合法区间(存在区间)，非法区间(不存在)）

low必须是低端.high是高端

唯一需要注意的是：循环条件是low<=high,不是low<high,mid=(.low+high)/2,该位置是low也是high，查找区间的最后一个点，还要比较。

while(low<=high)//合法范围
    {
        mid=(low+high)/2;//得到位置
 
        //开始对比（会产生三种情况：等于，大于，小于）
 
        if(ST.R[mid].key==key)  return mid;
        else if(key<ST.R[mid].key)  high=mid-1;
        else low=mid+1;
 
    }

①

 if(ST.R[mid].key==key)  return mid;

②

else if(key<ST.R[mid].key)  high=mid-1;

③

else low=mid+1;

①每次对比的元素，都是mid处的元素

执行到②③时，说明mid处的元素比较过且不是要找的元素！mid是中间位置那么接下来：“查找方向”有两个，要么“向左查找”high=mid-1,mid比较过，开始从下一个比较。要么“向右查找”， low=mid+1

区间向左 /向右偏移，通过low  high确定。

区间向左偏移，low本就在左，不用改变，改变high. high向左.

同理，区间向右偏移，low向右

key<ST.R[mid].key

key值小于“中间位置”那么key 应该存在于中间设置的左边，向左偏移 high向左

key>ST.R[mid].key

存在于右边

向右偏移，low向右。

折半查找的递归算法，函数的参数除了ST和·key，还需要加上low和high，修改一下else if和else的语句就可以了。

#include<iostream>
using namespace std;
 
typedef int Status;
#define  OK 1
#define ERROR 0
#define OVERFLOW -1
 
//typedef int ElemType;
typedef int KeyType; 
typedef int InfoType; 
 
 
typedef struct
{
    KeyType key;
    InfoType otherinfo;
}ElemType;
 
 
typedef struct
{
    ElemType* R;
    int length;
}SSTable;
 
//折半查找（二分查找）
//折半查找的前提条件是：顺序存储（下标==位置，地址），有序表。。。
 
//折半查找的非递归算法
int Search_Bin(SSTable ST,KeyType key)
{
    int low,high,mid;//限制范围，都是代表地址，位置。。。
 
    low=1;high=ST.length;
    while(low<=high)//合法范围
    {
        mid=(low+high)/2;//得到位置
 
        //开始对比（会产生三种情况：等于，大于，小于）
 
        if(ST.R[mid].key==key)  return mid;
        else if(key<ST.R[mid].key)  high=mid-1;
        else low=mid+1;
 
    }
 
 
    //查找失败（low>high  非法范围。。。)
    return 0;
}
 
 
 
//折半查找的递归算法(递归的是查找搜索的范围。。。每次范围缩小。。。极大地提高了效率)
 
int Search_Bin(SSTable ST,KeyType key,int low,int high)
{
    int low,high,mid;//限制范围，都是代表地址，位置。。。
 
    low=1;high=ST.length;
 
    while(low<=high)//合法范围
    {
        mid=(low+high)/2;//得到位置
 
        //开始对比（会产生三种情况：等于，大于，小于）
 
        if(ST.R[mid].key==key)  return mid;
        else if(key<ST.R[mid].key) Search_Bin(ST,key,low,mid-1) ;
        else Search_Bin(ST,key,mid+1,high);
 
    }
 
 
    //查找失败（low>high  非法范围。。。)
    return 0;
}
 
 
 
int main()
{
 
    return 0;
}