二分查找与二分答案(1)

 我们在写程序的时候,经常会遇到这样一类问题:在一个数组中查找一个数是不是存在。比如在下图的数组中,查找8是不是存在:

 如果不要求效率,我们最一般的查找方法就是顺序查找,依次查看a[0], a[1], …, a[n-1],检查是不是等于8。这样对于长度为n的数组,平均查找长度是n/2  如果数组是有序的,比如是递增的,就像上图[1, 2, 3, 4, 5, 7, 8, 10, 11, 13]一样的话。我们就有效率更高的查找算法,叫做二分查找。例如还是在上面数组中查找8

 第一步:我们直接找位于中间的数a[4],发现a[4]=5,比8要小,所以如果8在这个数组里,肯定在a[5]~a[9]之中  第二步:我们找a[5]-a[9]这个范围里位于中间的数a[7],发现a[7]=10,比我们要找的数大,所以如果8在这个数组里,肯定在a[5]-a[6]之中  第三步:我们找a[5]~a[6]这个范围里位于中间的数a[5],发现a[5]=7,比我们要找的8小。所以我们知道如果8在数组里,那它肯定是a[6]这个数  第四步也是最后一步。我们查看a[6]的值,发现a[6]=8,于是我们找到了8的位置。假如我们这时发现a[6]不是8,则说明8没有在这个数组里  二分查找又叫“折半查找”。因为我们每进行一步,也就是查看一个元素的数值,都会使得后面需要检查的范围缩小一半  二分查找的时间复杂度是O(logN)的,换句话说,在长度为N的有序数组中查找一个数,查看元素的次数最多是logN+1次。当N很大时,二分查找的速度比顺序查找快非常多倍

#include<iostream>
using namespace std;
int n,x,a[1000000];
int binary_search(int a[],int n,int x)
{
    int l = 0;
    int r = n - 1;
    int ans = -1;
    while(l <= r)
    {
        int m = (l + r) / 2;
        if(a[m] == x)
        {
            ans = m;
            break;
        }
        if(a[m] < x)
            l = m + 1;
        else
            r = m - 1;
    }
    return ans;
} 
int main()
{
    cin >> n >> x;
    for(int i = 0;i < n;i++)
        cin >> a[i];
    int ans = binary_search(a,n,x);
    cout << ans;
    return 0;
}

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

发表于

我来说两句

3 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

【Java学习笔记之三十三】详解Java中try,catch,finally的用法及分析

这一篇我们将会介绍java中try,catch,finally的用法 以下先给出try,catch用法: try {   //需要被检测的异常代码 } ca...

3029
来自专栏从流域到海域

《笨办法学Python》 第20课手记

《笨办法学Python》 第20课手记 本节课讲函数与文件,内容比较简单,但请注意常见问题解答,你应该记住那些内容。 指针表示存储地址。 原代码如下: from...

1896
来自专栏喵了个咪的博客空间

zephir-(8)类和对象1

#zephir-类和对象1# ? ##前言## 先在这里感谢各位zephir开源技术提供者 zephir全面使用对象编程,这就是为什么拓展的使用方式只能是方法和...

2713
来自专栏Java编程

《Effective Java》——读后总结

这本书在Java开发的行业里,颇有名气。今天总算是粗略的看完了...后面线程部分和序列化部分由于心浮气躁看的不仔细。这个月还剩下一周,慢慢总结消化。

4091
来自专栏张善友的专栏

深入浅出事件流处理NEsper(二)

NEsper使用的事件类型来描述事件的类型信息。你的应用在启动时可能预先配置定义事件类型,或者在运行时通过API或EPL语法动态的增加事件类型。 EPL中的cr...

18510
来自专栏帅小子的日常

freemarker的使用

32611
来自专栏Linux驱动

29.C++- 异常处理

C++内置了异常处理的语法元素 try catch try语句处理正常代码逻辑 当try语句发现异常时,则通过throw语句抛出异常,并退出try语句 catc...

2806
来自专栏程序员宝库

Java 中整型的缓存机制

本文将介绍Java中Integer的缓存相关知识。这是在Java 5中引入的一个有助于节省内存、提高性能的功能。首先看一个使用Integer的示例代码,从中学习...

763
来自专栏个人随笔

房上的猫:经典排序算法 - 冒泡排序Bubble sort

原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒...

34210
来自专栏帅小子的日常

freemarker的使用

732

扫码关注云+社区