文档章节

二分查找代码

o
 osc_odyg6b92
发布于 2018/07/13 11:43
字数 280
阅读 5
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

也叫折半查找。

优点:比较次数少,查找速度快,平均性能好。

缺点:查找的数组必须为排序好的数组。

时间复杂度:O(logN)

代码:(递归:用栈保存结果空间消耗严重)

#include <iostream>
using namespace std;
//二分查找  返回位置标号  时间复杂度O(logN)  
int binarySearch(int list[],int left,int right,int number)
{
    if(list==NULL)
        return -1;
    int index=0;
    int mid=(right+left)/2;
    if(left>right)
    {
        return -1;
    }
    if(number==list[mid])
    {
        index=mid;
        return index;
    }
    else if(number>list[mid])
    {
        binarySearch(list,mid+1,right,number);
    }
    else
    {
        binarySearch(list,left,mid-1,number);
    }
}
int main()
{
    int a[]={1,3,5,7,9,11,14,16,17,20};
    int left = 0;
    int right = sizeof(a)/sizeof(a[0])-1;
    int index =binarySearch(a,left,right,88);
    cout<<index<<endl;
    return 0;
}

非递归:(能用循环不用递归)

#include <iostream>
using namespace std;
//二分查找  返回位置标号  时间复杂度O(logN)  
int binarySearch(int list[],int left,int right,int number)
{
    if(list==NULL)
        return -1;
    while(left<right)
    {
        int mid=(right+left)/2;
        if(list[mid] == number)
        {
            return mid;
        }
        else if(number > list[mid])
        {
            left=mid+1;
        }
        else if(number < list[mid])
        {
            right=mid-1;
        }
    }
    return -1;
}
int main()
{
    int a[]={1,3,5,7,9,11,14,16,17,20};
    int left = 0;
    int right = sizeof(a)/sizeof(a[0])-1;
    int index =binarySearch(a,left,right,11);
    cout<<index<<endl;
    return 0;
}

 

o
粉丝 1
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Flappy Bird(安卓版)逆向分析(一)

更改每过一关的增长分数 反编译的步骤就不介绍了,我们直接来看反编译得到的文件夹 方法1:在smali目录下,我们看到org/andengine/,可以知晓游戏是由andengine引擎开发的。打开/res/raw/at...

enimey
2014/03/04
5.9K
18
代码生成器--Codgen

Codgen是一个基于数据库元数据模型,使用freemarker模板引擎来构建输出的代码生成器。freemarker的数据模型结构通常来说都是一个Map树状结构模型,codgen也不例外,它的数据模型这棵树的根节...

黄天政
2013/01/29
1.4W
2
数据库代码辅助工具--MaoCaiJun.Database

MaoCaiJun.DataBase 是一个用于 Microsoft Visual Studio 的数据库代码生成组件。它是基于 xml 文件的代码创建工具,支持sql2000,sql2005,sql2008,access, SQLite MaoCaiJun.Database 数据库...

mccj
2013/02/06
2.2K
1
C/C++ 代码文档生成器--cldoc

cldoc 是一个使用 clang 实现的 C/C++ 代码文档生成器。 特点: 使用 clang 可靠解析大多数复杂的 C++ 项目 零配置 使用 markdown 做为文档格式 生成描述 API 的 XML 文档 使用简单格式用于文...

匿名
2013/02/14
1.4K
0
代码检索工具--CodeQuery

CodeQuery 是一个用来搜索 C/C++、Java 源码的索引工具。基于 cscope 和 ctags 构建,使用 cqmakedb 工具来生成 CodeQuery 数据库文件,然后通过 GUI 工具进行查看。 支持搜索:符号、函数、...

匿名
2013/02/25
2.7K
0

没有更多内容

加载失败,请刷新页面

加载更多

如何在SQL Server中将多行文本合并为单个文本字符串?

问题: Consider a database table holding names, with three rows: 考虑一个包含名称的数据库表,该表具有三行: PeterPaulMary Is there an easy way to turn this into a single str......

富含淀粉
10分钟前
9
0
在JavaScript中生成特定范围内的随机整数? - Generating random whole numbers in JavaScript in a specific range?

问题: 如何可以生成两个指定的变量之间的随机整数在JavaScript中,例如x = 4和y = 8将输出任何的4, 5, 6, 7, 8 ? 解决方案: 参考一: https://stackoom.com/question/6PRz/在JavaScript中...

fyin1314
40分钟前
8
0
Vim清除最后一个搜索突出显示 - Vim clear last search highlighting

问题: Want to improve this post? 想要改善这篇文章吗? Provide detailed answers to this question, including citations and an explanation of why your answer is correct. 提供此问题......

技术盛宴
今天
23
0
马化腾每天刷 Leetcode?代码你打算写到几岁?

本文作者:o****0 前几天,一张未证真伪的截图流传,图中显示马化腾几乎每天都会在 Leetcode 上提交代码。 截图还贴出一个 Leetcode 账户地址。该地址的头像已从马化腾的照片换成腾讯 logo,...

百度开发者中心
前天
13
0
滴滴 3000+ Kylin Cube 背后的实践经验揭秘

本次分享主要有三个部分:Kylin 在滴滴的整体应用、架构的实践经验、滴滴全局字典最新版本的实现以及 Kylin 最新实时 OLAP 探索经验分享。 Kylin 在滴滴的应用&架构 Kylin 在滴滴的三类应用场...

浪尖聊大数据
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部