V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
x18960
V2EX  ›  Java

LintCode Classical Binary Search 二分法求助

  •  
  •   x18960 · 2017-07-28 10:46:30 +08:00 · 2306 次点击
    这是一个创建于 2435 天前的主题,其中的信息可能已经有所发展或是发生改变。

    这道题,我自己写的代码 直接查找并没有二分法 通过了,但是并不符合题目要求二分法
    然后想学习这个方法
    于是就百度
    http://m.blog.csdn.net/sinat_32547403/article/details/74931544
    LintCode 二分查找题总结 - 软件开发其他 - 红黑联盟
    http://www.2cto.com/kf/201608/534039.html

    这两个答案都是 boom 的,
    我学习半天这个方法 然后发现有问题.并不能查询到位置,
    例如
    solution.findPosition(new int[]{11,3,4,11,1,6,3,4},1);
    这样的就 boom

    当然 百度两种方法 排序完肯定能用,
    当然 如果排序了 也不用他们那么费劲. 直接取中间数比较就行吧,也不用加 start 值

    所以小弟在万能的 V2EX 求助一个 不用排序的这道题答案
    ps:最近被"本科"字眼打击太大,所以想闲暇时间学学这些简单的算法

    10 条回复    2017-08-03 07:55:58 +08:00
    rocksolid
        1
    rocksolid  
       2017-07-28 10:51:53 +08:00
    你还是先看下书吧
    这两个都写的很清楚针对有序数列,你非要拿个无序的来试
    DANG
        2
    DANG  
       2017-07-28 10:54:49 +08:00
    mymail 头像哈哈哈
    zetary
        3
    zetary  
       2017-07-28 10:56:44 +08:00 via Android
    …高中生都知道二分能用是因为单调
    yhf
        4
    yhf  
       2017-07-28 10:59:21 +08:00
    你给的这个数组既不是 sorted 也不是 rotated sorted, 怎么 binary search?
    lonenol
        5
    lonenol  
       2017-07-28 11:07:05 +08:00
    你要能发明一种方法用 lgn 的时间复杂度在无序数组里找到一个指定的数,下届图灵奖可能就颁给你了...这个发明可能会改变社会..
    x18960
        6
    x18960  
    OP
       2017-07-28 11:08:06 +08:00
    知道了, 题目自身就有限制,所以我审题不清 ,不过 我百度到的这两种写法 真的不咋高明....
    x18960
        7
    x18960  
    OP
       2017-07-28 11:08:26 +08:00
    @DANG 那是 QQ 邮箱图标
    em2046
        8
    em2046  
       2017-07-28 11:43:33 +08:00
    那用斐波那契查找?
    em2046
        9
    em2046  
       2017-08-02 22:25:20 +08:00
    @x18960 #6 除了使用斐波那契数列替代 /2 中点
    还可以把==与<的 2 次比较改成一次比较,不考虑等于的情况 减少一次比较
    虽然最好情况下变慢了,但是可以提升最坏情况时的效率
    x18960
        10
    x18960  
    OP
       2017-08-03 07:55:58 +08:00 via iPhone
    @em2046 好的,我研究一下。这个斐波那契数我都还不知道
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3265 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 63ms · UTC 14:03 · PVG 22:03 · LAX 07:03 · JFK 10:03
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.