《数据结构和算法分析》具有O(logN)对数特点的三个基本算法-阿里云开发者社区

开发者社区> cugwyman> 正文

《数据结构和算法分析》具有O(logN)对数特点的三个基本算法

简介: 对分查找 给定一个整数X和整数A0,A1,…,AN-1,后者已经预先排序并存在内存中,求使得Ai=X的下标i,如果X不在数据中,则返回i=-1。 int BinarySearch (const ElementType A[], ElementType x, int N)...
+关注继续查看

对分查找

给定一个整数X和整数A0,A1,…,AN-1,后者已经预先排序并存在内存中,求使得Ai=X的下标i,如果X不在数据中,则返回i=-1。

int BinarySearch (const ElementType A[], ElementType x, int N)
{
    int Low, Mid, High;

    Low = 0; High = N - 1;
    while (Low <= High)
    {
        Mid = (Low + High) / 2;
        if (A[Mid] < x)
            Low = Mid + 1;
        else if (A[Mid] > x)
            High = Mid - 1;
        else
            return Mid; //Found     
    }
    return NotFound //NotFound is defined as -1
}

欧几里得算法

计算两个整数的最大公因数(Gcd),通过连续计算余数直到余数是0为止,最后的非零余数就是最大公因数。

unsigned int Gcd (unsigned int M, unsigned int N)
{
    unsigned int Rem;

    while (N > 0)
    {
        Rem = M % N;
        M = N;
        N = Rem;
    }
    return M;
}

幂运算

递归算X^N

long int Pow (long int X;unsigned int N)
{
    if (N == 0)
        return 1;
    if (IsEven(N))
        return Pow (X * X, N / 2);
    else
        return Pow (X * X, N / 2) * X;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
GO基本数据结构练习:数组,切片,映射
按《GO IN ACTION》的书上进行。 应该是第二次了哦~~ package main import ( "fmt" ) func main() { array := [5]*int{0: new(int), 3: new(int)} *array[3] = 50 /* for k, v := range array { fmt.
719 0
一致性哈希算法的php实现与分析-算法
<?php/** 一致性哈希算法* 过程:* 1,抽象一个圆,然后把服务器节点按一定算法得到整数有序顺时针放到圆上,圆环用2^32 个点来进行均匀切割。* hash函数的结果应该均匀分布在[0,2^32-1]区间* 2,由于服务器少,在圆上分布不均匀会造成数据倾斜,所以我们使用虚拟节点代替服务器的节点,一个服务器生成32个虚拟节点,或者更多。
1373 0
HanLP 关键词提取算法分析详解
给定若干个句子,提取关键词。而TextRank算法是 graphbased ranking model,因此需要构造一个图,要想构造图,就需要确定图中的顶点如何构造,于是就把句子进行分词,将分得的每个词作为图中的顶点。
1198 0
RSA与AES混合加密算法的实现
RSA与AES加密算法所产生的密钥数不一样,它们是如何进行加密的呢? 接收方生成RSA密钥对,将其中的RSA公钥传递给发送方(接收方与发送方建立连接是需要认证的,SSL/TLS协议可以确保RSA公钥的安全完整),然后用RSA公钥对AES密钥进行加密,加密后的结果传递给接收方,接收方用RSA私钥解密后,得到AES密钥,最后使用AES密钥解密,从而达到安全互通数据的目的。(如下图所示)
1568 0
AGS无服务化分析基因数据 - mutect2 肿瘤样本分析
通过调用AGS的远程任务,可以完成一序列的基因数据的二级分析,不需要申请和持有云计算资源,就可以完成对海量数据的批量处理,目前可以支持人类全基因组,外显子,基因比对,宏基因组比对,Somatic胚系变异发现等业务场景的加速和低成本处理。 通过AGS调用mutect2任务来检测体细胞短突变, 短突变包括单核苷酸(SNV)以及插入和缺失(Indel)的改变。本文介绍如何通过AGS分析肿瘤样本。
392 0
h.264并行解码算法分析
并行算法类型可以分为两类 Function-level Decomposition,按照功能模块进行并行 Data-level Decomposition,按照数据划分进行并行   Function-level Decomposition 在h.
869 0
Silverlight中非对称加密及数字签名RSA算法的实现
RSA算法是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作,也很流行。它的安全性是基于大整数素因子分解的困难性,而大整数因子分解问题是数学上的著名难题,至今没有有效的方法予以解决,因此可以确保RSA算法的安全性。
669 0
开启数据智慧,阿里云大数据团队调研高新区
随着“云计算”、“互联网”、“物联网”的快速发展,大数据(Big Data)也吸引了越来越多的人关注,成为社会热点之一。大街小巷不论是技术人员、咨询人士以及各行各业的精英达人都在探讨着“大数据”,“大数据”显然已经成为新一代“网红”。
2013 0
+关注
cugwyman
CUG EE本科生,意向机器学习、计算机视觉。github.com/cugwyman
35
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载