无序数组可以折半查找吗? ----传说中的华为面试题目

一般对这道题目的描述大致如下:

已知：无序数组，折半查找，各元素值唯一。
函数原型是：
int Binary_Seach(int array[], int iValue, int iCount);
array是数组，在里面用折半查找的方法找等于iValue的值，找到返回1否则0，iCount是元素个数。

疑问:
无序数组可以用折半查找吗？
如果可以，那么为何教科书都写“折半查找有序数组”，难道这个是最近的重要发现？
(当然，教科书上没有规定"各元素值唯一",这个条件可能可以加快查找速度，
但是否能达到“折半”的程度，我表示怀疑)。

特别说明:
(1)在计算机行业，“折半查找”有一个技术指标，
那就是时间复杂度不大于O(logN),空间复杂度为O(1)。
这里，只要空间复杂度和时间复杂度的乘积不大于O(logN),
我们都认为是可以被称为“折半查找”的。
(2)这个帖子不讨论“折半查找”仅仅是一个语言游戏的情况。
(3)如果有实现了折半查找算法的朋友，希望给出复杂度分析。
类似“在1000000个数中进行查找，连1秒都不到”的论述没有任何价值。

好了，大家Go!!!

欢迎 UP JF MARK DING ....

114 个解决方案

#1

ding

#2

学习

#3

不敢想象！！！！

#4

可以查呀，就是我查不到嘛

#5

个人认为不可能!

#6

先排序再查找了!!不知道这样效率如何...

#7

要看你是如何理解“折半”这个词了，如果按传统意义上的“对有序线性序列进行折半匹配”的算法来讲，对无序序列执行此算法的结果将是不正确的。

但是，如果你理解“折半”只是一个查找顺序，而不做为一个判断方法，那么对于无序序列是可以用“折半”的顺序进行查找的。

#8

up .

#9

先排序再查找的话，效率就低了

不过一般的数据大多没有顺序吧

#10

如果是边找边排序呢？？？？

#11

那还不如循环查找

排序效率多低啊

#12

mark

我认为这个是绝对不可能的

#13

要先排序后才能进行折半查找，肯定的。
时间复杂度   排序     折半查找      总时间复杂度   线性扫描
             nlog(n)  log(n)        nlog(n)        n

  你对华为的面试官说你们出错题目了，恩。

#14

是文字游戏吧

#15

既然无序，何为折半，连标准都没有，除非是象我为了JF来打几个字。呵呵！：）

#16

这是不可能的。

#17

楼主,是可以找的!!!

只是找不到...

#18

楼上的名字很个性！！不如再来个：

屯屯屯屯屯屯屯屯屯屯屯屯屯屯屯屯屯屯屯屯

#19

不是题目出错，就是你题目记错，漏了什么重要条件。

#20

顺序查找 + 找完之后删除数组，时间O(n)，空间O(-n)，最终结果O(-n^2)XD

#21

那就是先排序后折半查找喽，有什么疑问吗？

#22

先排序后折半查找,不会是考虑反应的吧。

#23

就找一个数，直接按顺序找的话也比先排序找好啊。
化为的人有毛病吧，
无序拆半？

#24

我记得数据结构里面有个二分法
不知道折半查找的意义是什么。如果是二分法那直接告诉他 “it's impossible”

#25

#26

脑筋急转弯？

#27

无序折半？下一个一半应该取哪里呢？

#28

不要把简单的问题搞得这么复杂嘛！

不行就是不行。当然，你非得说行也可以，
impossible is nothing.
所以，你说行就行，你说不行就不行。

你说行别人说不行但是你说行就行。
你说不行别人说行但是你说不行就行。
别人说行你说不行就行。
别人说不行你说行就行。

所以你的思想决定着你的行与不行。
别人的想法不能决定你的行与不行。

……

累了，不打了：（

#29

如果没有其他条件的话，似乎不可能实现吧！

#30

我不知道怎么做
有没有知道我就不肯定了

楼主说的折半应该是说从时间复杂度和空间复杂度来考察吧
就是说时间复杂度和空间复杂度如果和折半算法相当就可以

大家继续

#31

无序,还找什么呀

#32

折半查找是在有序情况下进行比较查找，无序是不能查的

#33

我也觉得

#34

可以使用排序查找，就是算法是不是被优化那要看数据排列了。

#35

??无序滴？

#36

无序不能

#37

不行

#38

感觉能的。比如1。8。3。6。5。4。7。2。9中找5
顺序要第5次比较才能找到5
如题的算法先比较5，一下就能找到的。不是的话比较左边。没有再比较右边。
但是既然是折半的话每次都要计算在哪里折半。如果最后一个才找到的话。就比顺序查找多计算了logn次。其中底数为2。即logm+m<=n(底数为2),m/(e+1)<=n时，才是有用的。
个人认为多少有点概率的意思。蒙上算，蒙不上拉倒。所以有些场合是可以考虑的。一百多个
查找方法多数都是特定场合才能用的，通用的还是少的。
以上是个人的一点拙见，说的不好。大家见笑。

#39

to 楼上，你这样说不对，数字出现在任何一个位置的概率都一样的，如果5在第一个，用顺序查找第一个就找到了。没道理说如果用折半，命中概率就高了？如果测试10000次，这种所谓的折半查找肯定要比顺序查找慢。

#40

to楼上，注意我说的是某些场合才能用。
不过我上面写的计算等式是错的。这个我承认。
计算次数和比较次数是相等的。要这两个的和<=顺序查找的的次数才有效。就是
2*比较次数<=顺序查找的次数。
你说的第一个数是5，2*比较次数>顺序查找的次数,即2*1>1，这样当然是顺序查找效率高。
如果按照我写的数列2*1<5当然是这种高。

#41

对无序数组来说。是可以进行折半查找的。但是,就是有可能找不到正确的结果而已.所以返回0的情况比较多.只有对有序数组才能够找出正确的结果.

#42

有序数列才有"折半"查找的吧?

#43

to cymandhxl(sdfds)：
你说的某些场合是什么场合？要找的数字正好在中间？你觉得有意义吗?

#44

所谓的某些场合就是指有序才可以这么做，否则函数是不正确的。
如果我们允许不正确的函数，那我还可以构造出O(1)的函数来(只比较第一个元素，在某些场合他也可以得到正确结果)，那样又有什么意义呢？

#45

排序；折半查找

#46

看能不能接上点分～

#47

找

#48

可以的

int Binary_Seach(int array[], int iValue, int iCount){
   if(iCount > 0){
      array[0] = iValue;
      return 1;
   }
   return 0;
}

#49

折半查找正确的的前提就有序！
你现在是无序的，结果不保证正确的！
先用快速排序来一次，在折半查找

#50

折半想成分堆堆找就行了。

#1