LintCode Classical Binary Search 二分法求助

[x18960]

这道题,我自己写的代码 直接查找并没有二分法 通过了,但是并不符合题目要求二分法
然后想学习这个方法
于是就百度
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:最近被"本科"字眼打击太大,所以想闲暇时间学学这些简单的算法

[rocksolid]

你还是先看下书吧
这两个都写的很清楚针对有序数列，你非要拿个无序的来试

[DANG]

mymail 头像哈哈哈

[zetary]

…高中生都知道二分能用是因为单调

[yhf]

你给的这个数组既不是 sorted 也不是 rotated sorted, 怎么 binary search?

[lonenol]

你要能发明一种方法用 lgn 的时间复杂度在无序数组里找到一个指定的数,下届图灵奖可能就颁给你了...这个发明可能会改变社会..

[x18960]

知道了, 题目自身就有限制,所以我审题不清 ,不过 我百度到的这两种写法 真的不咋高明....

[x18960]

@DANG 那是 QQ 邮箱图标

[em2046]

那用斐波那契查找？

[em2046]

@x18960 #6 除了使用斐波那契数列替代 /2 中点
还可以把==与<的 2 次比较改成一次比较，不考虑等于的情况 减少一次比较
虽然最好情况下变慢了，但是可以提升最坏情况时的效率

[x18960]

@em2046 好的，我研究一下。这个斐波那契数我都还不知道