二分搜索技术

分治法的基本思想:将一个规模为n的问题,分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。递归的解这些子问题,然后将各个子问题的解合并得到原问题的解。

经典例子:二分搜索

算法基本思想:

1 将n个元素分成个数大致相同的两半,取n/2与x进行比较。

2 如果找到,则终止,返回。

3 如果小于n/2,则在小半部分继续查找。

4 如果大于n/2,则在大半部分继续查找。

算法描述代码:

#include <iostream>
using namespace std;

template <class Type>
int BinarySearch(Type a[],const Type &x,int n){
    int left=0;
    int right = n-1;
    while(left<=right){
        int middle = (left+right)/2;
        if(x == middle)
            return middle;
        if(x > a[middle])
            left = middle+1;
        else
            right = middle-1;
    }
    return -1;
}
int main()
{
    int num[10] = {0,9,8,7,6,5,4,3};
    int a;
    cout<<"输入想要查找的数字:"<<endl;
    cin>>a;
    int find = BinarySearch(num,a,9);
    if(find!=-1)
        cout<<find<<endl;
    else
        cout<<"找不到想要的结果"<<endl;
    return 0;
}

运行结果如下:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏landv

C语言介绍

4322
来自专栏Crossin的编程教室

【Python 第25课】 初探list

昨天课程里的例子有点没说清楚,有同学表示写在程序里发生了错误。因为我当时写这个代码片段时,心里假想着这是在一个函数的内部,所以用了return语句。如果你没有把...

3206
来自专栏顶级程序员

Python 工匠:善用变量来改善代码质量

我一直觉得编程某种意义上是一门『手艺』,因为优雅而高效的代码,就如同完美的手工艺品一样让人赏心悦目。

1223
来自专栏守候书阁

重构 - 用各种方式优化自己的函数库

最近有几天时间空闲,也是在学怎么写更有可读性的代码,更简单,方便的API。简单来说就是重构方面的内容。今天简单分享下,对以前一个小项目(ecDo,欢迎大家sta...

961
来自专栏PHP在线

5个经典的JavaScript面试题

在IT界中公司对JavaScript开发者的要求还是比较高的,但是如果JavaScript开 发者的技能和经验都达到了一定的级别,那他们还是很容易跳到优秀的公司...

3588
来自专栏我杨某人的青春满是悔恨

Swift API 设计指南(上)

本文翻译自苹果官方文档:Swift API Design Guidelines,如有错漏,欢迎指出。

1133
来自专栏斑斓

编程修炼 | Scala亮瞎Java的眼(二)

继续上一期的话题,介绍Scala有别于Java的特性。说些题外话,当我推荐Scala时,提出质疑最多的往往不是Java程序员,而是负责团队的管理者,尤其是略懂技...

3745
来自专栏Python小屋

Python中带else子句的for循环执行过程

这几天在厦门讲课,每天6小时,没有太多时间写新代码,宾馆不知道咋想的也不提供WiFi,只好用手机做个热点临时分享一点基础知识,300M的包月流量伤不起,热点瞬间...

2774
来自专栏工科狗和生物喵

【计算机本科补全计划】C++牛客网试题习题解析

正文之前 一大早醒来,外面淅淅沥沥的雨绵绵的下着,床铺真的舒服,但是我也不能就在床上刷微博看小说吧,所以想起了昨晚下载的牛客网的APP,赶紧掏出我的大宝贝---...

3867
来自专栏数说工作室

2. PRXPARSE () | 正则表达式的“阿赖耶识”

阿赖耶识...为宇宙万有之本,含藏万有,使之存而不失,故称藏识。又因其能含藏生长万有之种子,故亦称种子识。 ——《佛光大辞典》 佛家说人有九识,除眼、耳、鼻、...

3566

扫码关注云+社区

领取腾讯云代金券