问个问题binary search 的变体 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个问题binary search 的变体

问个问题binary search 的变体# JobHunting - 待字闺中

B*p2010-07-28 07:07

1 楼

Given a sorted array of strings which is interspersed with empty strings,
write a meth-
od to find the location of a given string
如果碰到空的str怎么办,找下一个非空的str,这样worst case就是o(n)不是o(logn)了
多谢

y*n2010-07-28 07:07

2 楼

说个傻傻的办法，扫描一遍，把非空的拷出来再做。
或者in place的挪成紧凑数组。

g*y2010-07-28 07:07

3 楼

那不也是O(n)吗

【在 y****n 的大作中提到】

: 说个傻傻的办法，扫描一遍，把非空的拷出来再做。
: 或者in place的挪成紧凑数组。

I*A2010-07-28 07:07

4 楼

随便扔砖头
这个题目说的不是很清楚
如果emptry string出现的次数不可以当成常量来看的话，假定是m,then the complexity is O(lg(n)+m)?
如果可以当成常量来看，就还是O(lg(n))。如果是空，可以检测它两侧。。。

【在 B*****p 的大作中提到】

: Given a sorted array of strings which is interspersed with empty strings,
: write a meth-
: od to find the location of a given string
: 如果碰到空的str怎么办,找下一个非空的str,这样worst case就是o(n)不是o(logn)了
: 多谢

f*32010-07-28 07:07

5 楼

careercup 上有这个题的答案
如果碰到空的str怎么办,找下一个非空的str,这样worst case就是o(n)不是o(logn)了
search(int start,int end){
mid=(start+end)/2;
while(str[mid]==' ') {mid++;}
r=strcmp(str1[mid+1,mid+1+str2.length()],str2);
if(r==0) return mid;
else if(r<0) search(mid+1,end);
else search(start,mid-1);
}