欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

查找算法:顺序查找、二分查找、分块查找

程序员文章站 2024-03-17 17:14:40
...

近期总结了各大排序算法的原理 ,并对其进行了实现,想着一并把查找算法总结了,今天就着手开始总结查找算法。

顺序查找

 关键字与数组中的数顺序比较,时间复杂度O(n).
void CGradationDlg::OnButfind() 
{
    // TODO: Add your control notification handler code here
    UpdateData(TRUE);
    int n=0;
    for (int i=0;i<10;i++)
    {
        if (num[i] == m_Find)
        {
            m_Result.Format("你要查找的数是输入的第%d个",i+1);
        }
        else
        {
            n++;
        }
    }
    if (n==10)
    {
        m_Result.Format("对不起,没有这个数!");
    }
    UpdateData(FALSE);
}

二分查找

二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好,占用系统内存较少;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

void CTwoAsunderDlg::Binary_Search(int key, int a[], int n)
{
    int low, high, mid, count = 0, count1 = 0;
    low = 0;
    high = n - 1;
    while (low < high)                              //当查找范围不为0时执行循环体语句
    {
        count++;                                //count记录查找次数
        mid = (low + high) / 2;                     //求出中间位置
        if (key < a[mid])                           //当key小于中间值
        {
            high = mid - 1;                     //确定左子表范围
        }
        else if (key > a[mid])                      //当key大于中间值
        {
            low = mid + 1;                          //确定右子表范围
        }
        else if (key == a[mid])                     //当key等于中间值证明查找成功
        {
            m_Result.Format("你要查找的数是输入的第%d个",mid+1);
            UpdateData(FALSE);
            count1++;                           //count1记录查找成功次数
            break;
        }
    }
    if (count1 == 0)                                //判断是否查找失败
    {
        m_Result.Format("对不起,没有这个数!");      //查找失败
    }
}

3分块查找

分块查找又称索引顺序查找,它是顺序查找的一种改进方法。
  方法描述:将n个数据元素”按块有序”划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须”按块有序”;即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;而第2块中任一元素又都必须小于第3块中的任一元素,……。
  操作步骤:
  step1 先选取各块中的最大关键字构成一个索引表;
  step2 查找分两个部分:先对索引表进行二分查找或
  顺序查找,以确定待查记录在哪一块中;

  然后,在已确定的块中用顺序法进行查找。
结构体index

void CBlockSearchDlg::OnButfind() 
{
    // TODO: Add your control notification handler code here
    UpdateData(TRUE);
    int i, j = 0, k;
    for (i = 1; i <= 3; i++)
    {
        index_table[i].start = j + 1;                   //确定每个块范围的起始值
        j = j + 1;
        index_table[i].end = j + 4;                     //确定每个块范围的结束值
        j = j + 4;
        index_table[i].key = num[j];                    //确定每个块范围中元素的最大值
    }
    k = Block_Search(m_Find, num);                      //调用函数进行查找
    if (k != 0)
    {
        m_Result.Format("你要查找的数是输入的第%d个",k);            //如果找到该数,则输出其位置
    }
    else
    {
        m_Result.Format("对不起,没有这个数!");                          //若未找到则输出提示信息
    }
    UpdateData(FALSE);
}
int CBlockSearchDlg::Block_Search(int key, int a[])
{
    int i, j;
    i = 1;
    while (i <= 3 && key > index_table[i].key)          //确定在那个块中
    {
        i++;
    }
    if (i > 3)                                  //大于分得的块数,则返回0
    {
        return 0;
    }
    j = index_table[i].start;                           //j等于块范围的起始值
    while (j <= index_table[i].end && a[j] != key)          //在确定的块内进行查找
    {
        j++;
    }
    if (j > index_table[i].end)                     //如果大于块范围的结束值,则说明没有要查找的数,j置0
    {
        j = 0;
    }
    return j;
}
相关标签: 算法 排序算法