谁帮俺看看OSK，抄的底，卖还是留。 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Stock

谁帮俺看看OSK，抄的底，卖还是留。

谁帮俺看看OSK，抄的底，卖还是留。# Stock

j*e2010-12-07 08:12

1 楼

Given an array of sorted numbers, a number to search for and a condition
such as GreaterThanEquals, LessThan etc, return the match if present and the
index. Please use simple linear search, can not use binary search tree. The
array is either in descending order or in ascending order.
这是道超级简单的面试题吗？还是到难题？有什么TRICKY的地方？
刷题大牛们，分析一下。
多谢。

g*u2010-12-07 08:12

2 楼

不回答，俺就卖一半了。

j*e2010-12-07 08:12

3 楼

是因为有不同种的操作符，如果一个操作一个函数，几个函数会重合很多，所以需要找
到一个方式，写尽可能少的CODE吗，比如说一个函数就覆盖所有的操作。

j*e2010-12-07 08:12

4 楼

有没有大牛吱一声？
这道题看似简单，实则很容易产生很多重复的CODE。因为LESS THAN 和GREATER THAN是
对称的，同事，数组又有升序和降序两种情况，组合起来是4种情况，很容易产生重复
CODE.
有什么好的方法没有？

a*n2010-12-07 08:12

5 楼

估计是在一开始判断升序或降序， set a flag，然后直接用greaterthan or
lessthan

the
The

【在 j*****e 的大作中提到】

: Given an array of sorted numbers, a number to search for and a condition
: such as GreaterThanEquals, LessThan etc, return the match if present and the
: index. Please use simple linear search, can not use binary search tree. The
: array is either in descending order or in ascending order.
: 这是道超级简单的面试题吗？还是到难题？有什么TRICKY的地方？
: 刷题大牛们，分析一下。
: 多谢。

l*i2010-12-07 08:12

6 楼

Use functor, example std::greater

j*e2010-12-07 08:12

7 楼

我试着用C写了一下。也是先判断升序降序，然后是分LESS THAN, LESS THAN EQUAL,
GREATER THAN, GREATER THAN EQUAL, EQUAL，一共5中情况，然后每种情况的区别主
要是>，还是CODE显得很繁琐。
哪位大牛能举个FUNCTOR的例子。
多谢。
//升序
case( LessThan ):
{
i = 0;
while ( ( items[ i ] < key ) )
i++;
if( ( i == num_elems ) || ( ( elem[ i ] >= key ) && ( i == 0 ) ) )
result= NotExist;
else
{
*index = i - 1;
result = FoundResult;
}
break;
}
//降序 GREATER THAN
case( GreaterThan ):
{
i = 0;
while ( ( elems[ i ] < key ) )
i++;
if( ( i == num_elems ) || ( ( elems[ i ] == key ) && ( i == 0 ) ) )
result= NotExist;
else
{
*index = i;
result = Found;
}
break;
}