二分查找与二分答案(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;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏kalifaの日々

美团北京视频面试题目

1.用过makefile吗 2.python的多线程是真正的多线程吗? 3.写一个冒牌排序,再写一个递归的冒泡排序 4.写一个单链表反转,十几行代码以内 ...

772
来自专栏Albert陈凯

JAVA基础面试题

JAVA 说出ArrayList, Vector, LinkedList的存储性能和特性(集合类:ArrayList与 LinkedList的区别,为什么JAV...

3387
来自专栏mathor

LeetCode90. 子集 II

 升级版子集问题,最简单的办法,先把所有元素存储到set中去重,然后再重新赋值给数组,再dfs,但这样做太简单了,没什么难度,于是换了一种做法,不去重,直...

1602
来自专栏逆向技术

C++反汇编第二讲,不同作用域下的构造和析构的识别

               C++反汇编第二讲,不同作用域下的构造和析构的识别 目录大纲:   1.全局(静态)对象的识别,(全局静态全局一样的,都是编译期间...

18810
来自专栏精讲JAVA

Java面试基础必备知识点,怼死面试官,从我做起

小海哥有话说 感觉最近支持我的人越来越多,谢谢大家,大家找到工作才是最重要的,我还是那句话,喜欢的就关注,想看深入研究的东西,等我更新完面试系列...

5548
来自专栏java一日一条

Java 泛型一览笔录

泛型(Generics )是把类型参数化,运用于类、接口、方法中,可以通过执行泛型类型调用 分配一个类型,将用分配的具体类型替换泛型类型。然后,所分配的类型将用...

871
来自专栏nnngu

Java面试题库及答案解析

1、面向对象编程(OOP)有哪些优点? 代码开发模块化,更易维护和修改。 代码复用。 增强代码的可靠性和灵活性。 增加代码的可理解性。 2、面向对象编程有哪些特...

3035
来自专栏数据结构笔记

数据结构(一):什么是数据结构

数据的逻辑结构是从逻辑关系上描述数据(主要是相邻关系,比如栈、队列、链表等),它与数据的存储无关,是独立于计算机的。因此,数据结构可以看作从具体问题中抽象...

1484
来自专栏Java编程技术

并发队列中迭代器弱一致性原理探究

并发队列里面的Iterators是弱一致性的,next返回的是队列某一个时间点或者创建迭代器时候的状态的反映。当创建迭代器后,其他线程删除了该元素时候并不会抛出...

1321
来自专栏黑泽君的专栏

finally关键字的特点及其面试题

881

扫码关注云+社区