一道A家店面题求解 - 未名空间MITBBS历史存档

w*g2013-02-03 08:02

1 楼

【以下文字转载自 Family 讨论区】
发信人: ccccmm (猪喂曼玉), 信区: Family
标题: 这年头ons也要被人肉了. (转载)
发信站: BBS 未名空间站 (Fri Feb 12 19:12:15 2010, 美东)
发信人: Epoxy (A & B), 信区: SanFrancisco
标题: 这年头ons也要被人肉了.
发信站: BBS 未名空间站 (Fri Feb 12 17:23:29 2010, 美东)
http://www.newsmth.net/bbstcon.php?board=Oversea&gid=2371036

f*u2013-02-03 08:02

2 楼

给定一个ordered array，int型，无重复元素，元素个数大于零，可能是升序，也可能
是降序。现在任给一个int key，需要实现这些可能的搜索：找出小于这个key的最大元
素，找出大于这个key的最小元素，找出这个key本身，找出小于或者等于这个key的最
大元素，找出大于或者等于这个key的最小元素。要求返回搜索结果。必须用C/C++。
代码不难写，但是要求避免重复代码，让代码尽可能短，同时要求代码可维护性高，也
就是易读。可是对于不同的搜索，完全避免重复代码有点不好办。
我试图写一段通用的代码能针对各种不同的搜索，发现很难。我用switch，对每种搜索
单独求解，然后根据key相对array的位置分类，再用switch，可是无法避免每种不同情
况下代码或多或少会有重复。想看看这里的高手有没有妙招能避免代码重复。

m*n2013-02-03 08:02

3 楼

这女的也够傻比的。

j*y2013-02-03 08:02

4 楼

array里面的数字有 duplicate吗？

【在 f*****u 的大作中提到】

: 给定一个ordered array，int型，无重复元素，元素个数大于零，可能是升序，也可能
: 是降序。现在任给一个int key，需要实现这些可能的搜索：找出小于这个key的最大元
: 素，找出大于这个key的最小元素，找出这个key本身，找出小于或者等于这个key的最
: 大元素，找出大于或者等于这个key的最小元素。要求返回搜索结果。必须用C/C++。
: 代码不难写，但是要求避免重复代码，让代码尽可能短，同时要求代码可维护性高，也
: 就是易读。可是对于不同的搜索，完全避免重复代码有点不好办。
: 我试图写一段通用的代码能针对各种不同的搜索，发现很难。我用switch，对每种搜索
: 单独求解，然后根据key相对array的位置分类，再用switch，可是无法避免每种不同情
: 况下代码或多或少会有重复。想看看这里的高手有没有妙招能避免代码重复。

j*y2013-02-03 08:02

5 楼

先比较 A[0] 和 A[n - 1]?

【在 f*****u 的大作中提到】

: 给定一个ordered array，int型，无重复元素，元素个数大于零，可能是升序，也可能
: 是降序。现在任给一个int key，需要实现这些可能的搜索：找出小于这个key的最大元
: 素，找出大于这个key的最小元素，找出这个key本身，找出小于或者等于这个key的最
: 大元素，找出大于或者等于这个key的最小元素。要求返回搜索结果。必须用C/C++。
: 代码不难写，但是要求避免重复代码，让代码尽可能短，同时要求代码可维护性高，也
: 就是易读。可是对于不同的搜索，完全避免重复代码有点不好办。
: 我试图写一段通用的代码能针对各种不同的搜索，发现很难。我用switch，对每种搜索
: 单独求解，然后根据key相对array的位置分类，再用switch，可是无法避免每种不同情
: 况下代码或多或少会有重复。想看看这里的高手有没有妙招能避免代码重复。

f*u2013-02-03 08:02

6 楼

元素无重复，更新帖子了。

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

: array里面的数字有 duplicate吗？

p*22013-02-03 08:02

7 楼

感觉不是太好写。

l*a2013-02-03 08:02

8 楼

scala也不成？

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

: 感觉不是太好写。

p*22013-02-03 08:02

9 楼

scala倒是很容易。

【在 l*****a 的大作中提到】

: scala也不成？

f*u2013-02-03 08:02

10 楼

我就是这么做的，现在主要问题是怎么避免重复代码。我用两层switch，一层对搜索类
型分类，内层对key相对array的位置分类（a[0]之前，a[n-1]之后，两者之间，。。。
）每种情况单独写一段搜索代码，结果代码总共500行。A家的要求是避免代码重复，尽
可能短，但是又要易读，易维护。

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

: 先比较 A[0] 和 A[n - 1]?

i*e2013-02-03 08:02

11 楼

pass function pointer (ie, use functor) as the comparison function.
Apply binary search since it's an ordered array. Different comparison
functions should allow you to cover all cases elegantly.

【在 f*****u 的大作中提到】

: 给定一个ordered array，int型，无重复元素，元素个数大于零，可能是升序，也可能
: 是降序。现在任给一个int key，需要实现这些可能的搜索：找出小于这个key的最大元
: 素，找出大于这个key的最小元素，找出这个key本身，找出小于或者等于这个key的最
: 大元素，找出大于或者等于这个key的最小元素。要求返回搜索结果。必须用C/C++。
: 代码不难写，但是要求避免重复代码，让代码尽可能短，同时要求代码可维护性高，也
: 就是易读。可是对于不同的搜索，完全避免重复代码有点不好办。
: 我试图写一段通用的代码能针对各种不同的搜索，发现很难。我用switch，对每种搜索
: 单独求解，然后根据key相对array的位置分类，再用switch，可是无法避免每种不同情
: 况下代码或多或少会有重复。想看看这里的高手有没有妙招能避免代码重复。

e*o2013-02-03 08:02

12 楼

输出一个range行么，这样就可以实现这机会总查找。当然还是得先比较 a[0]. a[n-1
].

【在 f*****u 的大作中提到】

: 我就是这么做的，现在主要问题是怎么避免重复代码。我用两层switch，一层对搜索类
: 型分类，内层对key相对array的位置分类（a[0]之前，a[n-1]之后，两者之间，。。。
: ）每种情况单独写一段搜索代码，结果代码总共500行。A家的要求是避免代码重复，尽
: 可能短，但是又要易读，易维护。

f*u2013-02-03 08:02

13 楼

面试官要求只能用linear search。这个functor是啥，我好好看看。

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

: pass function pointer (ie, use functor) as the comparison function.
: Apply binary search since it's an ordered array. Different comparison
: functions should allow you to cover all cases elegantly.

p*22013-02-03 08:02

14 楼

linear search太好了。

【在 f*****u 的大作中提到】

: 面试官要求只能用linear search。这个functor是啥，我好好看看。

f*u2013-02-03 08:02

15 楼

只能输出找到或者没找到，找到的话找到的是什么，是key本身还是小于key的最大，或
者是大于key的最小。

-1

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

: 输出一个range行么，这样就可以实现这机会总查找。当然还是得先比较 a[0]. a[n-1
: ].

c*t2013-02-03 08:02

16 楼

这个店面够狠啊，要求很高
如果是我，我就先写出来重复代码的，再简化，否则非陷入到判断逻辑混乱中不可。
先定义method如下， asc是升序, type是enumerate
type=1 找出小于这个key的最大元素
type=2 找出大于这个key的最小元素
type=3 找出这个key本身
type=4 找出小于或者等于这个key的最大元素
type=5 找出大于或者等于这个key的最小元素
int findKey(int[] arr, int key, boolean asc, int type){
}
程序外包给大牛们完成吧。

【在 f*****u 的大作中提到】

: 给定一个ordered array，int型，无重复元素，元素个数大于零，可能是升序，也可能
: 是降序。现在任给一个int key，需要实现这些可能的搜索：找出小于这个key的最大元
: 素，找出大于这个key的最小元素，找出这个key本身，找出小于或者等于这个key的最
: 大元素，找出大于或者等于这个key的最小元素。要求返回搜索结果。必须用C/C++。
: 代码不难写，但是要求避免重复代码，让代码尽可能短，同时要求代码可维护性高，也
: 就是易读。可是对于不同的搜索，完全避免重复代码有点不好办。
: 我试图写一段通用的代码能针对各种不同的搜索，发现很难。我用switch，对每种搜索
: 单独求解，然后根据key相对array的位置分类，再用switch，可是无法避免每种不同情
: 况下代码或多或少会有重复。想看看这里的高手有没有妙招能避免代码重复。

c*t2013-02-03 08:02

17 楼

linear search啊？太失望了！那要排序干啥？

【在 f*****u 的大作中提到】

: 面试官要求只能用linear search。这个functor是啥，我好好看看。

p*22013-02-03 08:02

18 楼

val lessMax=(x:Int, k:Int)=>xval moreMin=(x:Int, k:Int)=>x>k
val equals=(x:Int, k:Int)=>x==k
val lessEqualsMax=(x:Int, k:Int)=>x<=k
val moreEqualsMax=(x:Int, k:Int)=>x>=k
def search(arr:Array[Int], target:Int, comparator:(Int,Int)=>Boolean,
first:Boolean):Int={
val list=for(iif(first) list.head else list.last
}

c*t2013-02-03 08:02

19 楼

看来这个语言必须在竞赛与面试中禁用了。

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

: val lessMax=(x:Int, k:Int)=>x: val moreMin=(x:Int, k:Int)=>x>k
: val equals=(x:Int, k:Int)=>x==k
: val lessEqualsMax=(x:Int, k:Int)=>x<=k
: val moreEqualsMax=(x:Int, k:Int)=>x>=k
: def search(arr:Array[Int], target:Int, comparator:(Int,Int)=>Boolean,
: first:Boolean):Int={
: val list=for(i: if(first) list.head else list.last
: }

s*n2013-02-03 08:02

20 楼

写一个找到小于k的最大的元素的函数。
然后利用它来写exactk, minlarger, lessOrexact, largerorexact.
这是实践中常用方法。

【在 f*****u 的大作中提到】

: 给定一个ordered array，int型，无重复元素，元素个数大于零，可能是升序，也可能
: 是降序。现在任给一个int key，需要实现这些可能的搜索：找出小于这个key的最大元
: 素，找出大于这个key的最小元素，找出这个key本身，找出小于或者等于这个key的最
: 大元素，找出大于或者等于这个key的最小元素。要求返回搜索结果。必须用C/C++。
: 代码不难写，但是要求避免重复代码，让代码尽可能短，同时要求代码可维护性高，也
: 就是易读。可是对于不同的搜索，完全避免重复代码有点不好办。
: 我试图写一段通用的代码能针对各种不同的搜索，发现很难。我用switch，对每种搜索
: 单独求解，然后根据key相对array的位置分类，再用switch，可是无法避免每种不同情
: 况下代码或多或少会有重复。想看看这里的高手有没有妙招能避免代码重复。

c*s2013-02-03 08:02

21 楼

如果允许用这种函数的话，
那用java的Arrays.binarySearch(int[] A, int key)也是很简单的事情啊。
代码也就几行啊。

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

: val lessMax=(x:Int, k:Int)=>x: val moreMin=(x:Int, k:Int)=>x>k
: val equals=(x:Int, k:Int)=>x==k
: val lessEqualsMax=(x:Int, k:Int)=>x<=k
: val moreEqualsMax=(x:Int, k:Int)=>x>=k
: def search(arr:Array[Int], target:Int, comparator:(Int,Int)=>Boolean,
: first:Boolean):Int={
: val list=for(i: if(first) list.head else list.last
: }

s*02013-02-03 08:02

22 楼

正解

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

: 写一个找到小于k的最大的元素的函数。
: 然后利用它来写exactk, minlarger, lessOrexact, largerorexact.
: 这是实践中常用方法。

p*22013-02-03 08:02

23 楼

写一个看看。

【在 c***s 的大作中提到】

: 如果允许用这种函数的话，
: 那用java的Arrays.binarySearch(int[] A, int key)也是很简单的事情啊。
: 代码也就几行啊。

U*52013-02-03 08:02

24 楼

这个题考的是generic programming.
你自己写 compare functor，根据input 第一个和最后一个元素判断,和须要搜索的类
型，可能要写不一样的， pass到
STL transform里，应该就行了

【在 f*****u 的大作中提到】

: 给定一个ordered array，int型，无重复元素，元素个数大于零，可能是升序，也可能
: 是降序。现在任给一个int key，需要实现这些可能的搜索：找出小于这个key的最大元
: 素，找出大于这个key的最小元素，找出这个key本身，找出小于或者等于这个key的最
: 大元素，找出大于或者等于这个key的最小元素。要求返回搜索结果。必须用C/C++。
: 代码不难写，但是要求避免重复代码，让代码尽可能短，同时要求代码可维护性高，也
: 就是易读。可是对于不同的搜索，完全避免重复代码有点不好办。
: 我试图写一段通用的代码能针对各种不同的搜索，发现很难。我用switch，对每种搜索
: 单独求解，然后根据key相对array的位置分类，再用switch，可是无法避免每种不同情
: 况下代码或多或少会有重复。想看看这里的高手有没有妙招能避免代码重复。

s*02013-02-03 08:02

25 楼

写一个看看

【在 U***5 的大作中提到】

: 这个题考的是generic programming.
: 你自己写 compare functor，根据input 第一个和最后一个元素判断,和须要搜索的类
: 型，可能要写不一样的， pass到
: STL transform里，应该就行了

U*52013-02-03 08:02

26 楼

嗯，回头有空试试。

【在 s****0 的大作中提到】

:
: 写一个看看

s*02013-02-03 08:02

27 楼

大概是这个意思. 我没理解最后两种情况怎么处理，好像结果不确定。
package myutil;
import java.util.Arrays;
public class FlexSearch {
final Integer[] data;
final boolean asc;
public FlexSearch(Integer[] data) {
if (data == null || data.length < 2)
throw new java.lang.NoSuchFieldError();// whatever.
this.data = data;
asc = data[0] - data[1] < 0;
}
private int getIdx(int val) {
return Arrays.binarySearch(data, val);
}
public int getLTMax(int val) {
int idx = getIdx(val - 1);
if (idx >= 0)
return data[idx];
idx = -idx - 2;
if (idx >= 0 && idx < data.length)
return data[idx];
return Integer.MIN_VALUE;
}
public int getGTMin(int val) {
int idx = getIdx(val + 1);
if (idx >= 0)
return data[idx];
idx = -idx - 1;
if (idx >= 0 && idx < data.length)
return data[idx];
return Integer.MIN_VALUE;
}
public static void main(String[] args) {
Integer[] data = { 2, 4, 6, 8, 10 };
FlexSearch fsch = new FlexSearch(data);
for (Integer val : new Integer[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
}) {
System.out.println(val + ": " + fsch.getIdx(val) + ", "
+ fsch.getLTMax(val) + ", " + fsch.getGTMin(val));
}
}
}

s*02013-02-03 08:02

28 楼

无重复元素。。。找出小于或者‘等于’这个key的最大元素

J*92013-02-03 08:02

29 楼

It's simple binary search...

【在 f*****u 的大作中提到】

: 给定一个ordered array，int型，无重复元素，元素个数大于零，可能是升序，也可能
: 是降序。现在任给一个int key，需要实现这些可能的搜索：找出小于这个key的最大元
: 素，找出大于这个key的最小元素，找出这个key本身，找出小于或者等于这个key的最
: 大元素，找出大于或者等于这个key的最小元素。要求返回搜索结果。必须用C/C++。
: 代码不难写，但是要求避免重复代码，让代码尽可能短，同时要求代码可维护性高，也
: 就是易读。可是对于不同的搜索，完全避免重复代码有点不好办。
: 我试图写一段通用的代码能针对各种不同的搜索，发现很难。我用switch，对每种搜索
: 单独求解，然后根据key相对array的位置分类，再用switch，可是无法避免每种不同情
: 况下代码或多或少会有重复。想看看这里的高手有没有妙招能避免代码重复。

p*22013-02-03 08:02

30 楼

LZ说了，要linear search

【在 J**9 的大作中提到】

: It's simple binary search...

A*i2013-02-03 08:02

31 楼

我承认自己水平太次
但是linear search? 莫非不是一个一个查过去找到k然后它之前和它之后的不就是要的
结果么？
或者linear search有别的定义？

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

:
: LZ说了，要linear search

p*22013-02-03 08:02

32 楼

他题目的意思应该不是找到所有的。每次只找一个。所以考点是传comparator函数进去
。根据传进去的函数返回结果。很像FP的思路。

【在 A*****i 的大作中提到】

: 我承认自己水平太次
: 但是linear search? 莫非不是一个一个查过去找到k然后它之前和它之后的不就是要的
: 结果么？
: 或者linear search有别的定义？

U*52013-02-03 08:02

33 楼

一边看球一边草草写了写，corner case没时间搞了，只写了头2个search的情况：
小于key的最大值 - op_max_less
大于key的最小值 - op_min_great
其他几种情况自己加Functor就是了。感觉myfind return那里比较繁琐，应该有更好办
法整理一下。
写得不好，轻拍。
//Compare.h
enum Op_code
{
op_max_less = 0,
op_min_great
};
class Less
{
public:
Less(int v): val_(v), op_(op_max_less){}
bool operator()(int v1)
{
return v1 < val_;
}
const Op_code op_;
private:
int val_;

};
class Greater
{
public:
Greater(int v): val_(v), op_(op_min_great){}
bool operator()(int v1)
{
return v1 > val_;
}
const Op_code op_;
private:
int val_;
};
template
int myfind( int* begin, int* end, Comp comp)
{
bool asc = (*begin < *end);
while( begin+1 != end)
{
if( comp( *begin) && !comp( *(begin+1)))
break;
++begin;
}
switch (comp.op_)
{
case op_max_less:
if( asc)
return *begin;
else
return *(begin+1);
case op_min_great:
if( asc)
return *(begin+1);
else
return *begin;
default:
return *begin;
}
}
---
//test.cpp
#include
#include "Compare.h"
using namespace std;
int main()
{
int ary1[10] = {1,2,3,4,5,7,8,9,10,11};
int ary2[10] = {11,10,9,8,7,6,4,3,2,1};
Less less(6);
Greater greater(5);
cout << myfind(ary1, ary1+9, less) << endl;
cout << myfind(ary2, ary2+9, greater)<< endl;
return 0;
}

J*92013-02-03 08:02

34 楼

How about this direction?
=====================================
/// array is sorted in Ascending order
int binarySearchAscending(int array[], int key, int low, int high)
{
int mid;
if(!array|| (low>high))
return -1;

while(high >= low)
{
mid = low+(high-low)/2;
if(key < array[mid])
high = mid-1;
else if (key > array[mid])
low = mid+1;
else
return mid;
}

return -1;
}
/// array is sorted in Descending order
int binarySearchDescending(int array[], int key, int low, int high)
{
int mid;

if(!array|| (low>high))
return -1;

while(high >= low)
{
mid = low+(high-low)/2;
if(key > array[mid])
high = mid-1;
else if (key < array[mid])
low = mid+1;
else
return mid;
}

return -1;
}
typedef enum searchType {
searchExact,
lessMax,
largerMin,
lessEqualMax,
largerEqualMin,
Undefined
} searchType;
int binarySearchAny(int array[], int size, int key, searchType type)
{
if(!array|| (size<1))
return -1;
int isAscending = (array[0] <= array[size-1]);
int idx = -1;
if (isAscending)
idx = binarySearchAscending(array, key, 0, size-1);
else
idx = binarySearchDescending(array, key, 0, size-1);
if (idx == -1)
return -1; /// key not in array: Assume we don't handle further
switch (type)
{
case searchExact:
break;
case lessMax:
{
if (isAscending)
idx--;
else
idx++;
break;
}
case largerMin:
{
if (isAscending)
idx++;
else
idx--;
break;
break;
}
case lessEqualMax:
{
if (isAscending)
idx--;
else
idx++;
break;
}
case largerEqualMin:
{
if (isAscending)
idx--;
else
idx++;
break;
}
default:
return -1;
}
return idx;
}

e*e2013-02-03 08:02

35 楼

按这个思路上代码，五个函数实现了四个，第五个和第四个很类似，就不写了。函数返
回的是数组下标，caller可以用a[i]来获得值，此时数组a是递增的。
public void find(int[] a, int key) {
int n = a.length;
boolean ascending = ( a[n-1] - a[0] > 0 );
if ( !ascending )
reverse( a );
// caller调用五个函数,此出省略.
}
public int maxLessThan(int[] a, int key) {
int n = a.length;
for ( int i = 0; i < n; i++ ) {
if ( a[i] >= key )
return --i;
}
return n-1;
}

public int minMoreThan(int[] a, int key) {
int maxLTPos = maxLessThan( a, key );
if ( maxLTPos == a.length - 1 )
return -1;
if ( a[maxLTPos + 1] == key )
return maxLTPos + 2;
else
return maxLTPos + 1;
}

public int exact(int[] a, int key) {
int maxLTPos = maxLessThan( a, key );
int minMTPos = minMoreThan( a, key );

if ( minMTPos != -1 && minMTPos - maxLTPos == 2 )
return minMTPos -1;
if ( minMTPos == -1 && maxLTPos == a.length -2 )
return a.length - 1;

return -1;
}

public int maxEqualOrLessThan(int[] a, int key) {
int maxLTPos = maxLessThan( a, key );
int exactPos = exact( a, key );

if ( exactPos == -1 && maxLTPos != -1 )
return maxLTPos;
if ( exactPos != -1 && exactPos - maxLTPos == 1 )
return exactPos;

return -1;
}

private void reverse(int[] a) {
int n = a.length;
for ( int i = 0; i < n/2; i++ ) {
int temp = a[i];
a[i] = a[n-1-i];
a[n-1-i] = temp;
}
}

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

: 写一个找到小于k的最大的元素的函数。
: 然后利用它来写exactk, minlarger, lessOrexact, largerorexact.
: 这是实践中常用方法。

t*t2013-02-03 08:02

36 楼

晕了, 这么点要求要写500行? 你写的不是汇编?

【在 f*****u 的大作中提到】

: 我就是这么做的，现在主要问题是怎么避免重复代码。我用两层switch，一层对搜索类
: 型分类，内层对key相对array的位置分类（a[0]之前，a[n-1]之后，两者之间，。。。
: ）每种情况单独写一段搜索代码，结果代码总共500行。A家的要求是避免代码重复，尽
: 可能短，但是又要易读，易维护。

t*t2013-02-03 08:02

37 楼

要的是C++, 不要java.

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

:
: 按这个思路上代码，五个函数实现了四个，第五个和第四个很类似，就不写了。函数返
: 回的是数组下标，caller可以用a[i]来获得值，此时数组a是递增的。
: public void find(int[] a, int key) {
: int n = a.length;
: boolean ascending = ( a[n-1] - a[0] > 0 );
: if ( !ascending )
: reverse( a );
: // caller调用五个函数,此出省略.
: }

G*A2013-02-03 08:02

38 楼

看到了。总觉得lz是不是题目没听对

【在 s****0 的大作中提到】

: 无重复元素。。。找出小于或者‘等于’这个key的最大元素

p*22013-02-03 08:02

39 楼

有说是C＋＋吗？

【在 t****t 的大作中提到】

: 要的是C++, 不要java.

e*e2013-02-03 08:02

40 楼

解这个题，C++和java没多大差别吧。

【在 t****t 的大作中提到】

: 要的是C++, 不要java.

l*b2013-02-03 08:02

41 楼

函数指针20行差不多能搞定吧

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

:
: 有说是C＋＋吗？

t*t2013-02-03 08:02

42 楼

#include
#include
enum search_type { Exact, MaxLess, MinGreater, MaxLessEqual, MinGreaterEqual
};
/* returns "next" element if key was to be inserted. */
template
typename Container::const_iterator
search_place(const Container& array, typename Container::value_type key,
bool ascending)
{
if (ascending) {
return lower_bound(array.begin(), array.end(), key, std::less<
typename Container::value_type>());
} else {
return lower_bound(array.begin(), array.end(), key, std::greater<
typename Container::value_type>());
}
}
template
bool search(const Container& array, typename Container::value_type key,
search_type type, typename Container::value_type& result)
{
bool ascending = array.front()empty...
auto position = search_place(array, key, ascending);
bool equal = (position!=array.end() && *position==key);
if (!ascending) {
/* normalize the search type */
switch (type) {
case MaxLess: type=MinGreater; break;
case MaxLessEqual: type=MinGreaterEqual; break;
case MinGreater: type=MaxLess; break;
case MinGreaterEqual: type=MaxLessEqual; break;
default: ;
}
}
switch (type) {
case Exact:
if (equal) result=key;
return equal;
case MaxLessEqual:
if (equal) {
result=key; return true;
}
/* fallthrough */
case MaxLess:
if (position!=array.begin()) {
result=position[-1]; return true;
} else {
return false;
}
case MinGreater:
if (equal) ++position;
/* fallthrough */
case MinGreaterEqual:
if (position!=array.end()) {
result=*position; return true;
} else {
return false;
}
}
}

e*e2013-02-03 08:02

43 楼

写一个吧.

【在 l*******b 的大作中提到】

: 函数指针20行差不多能搞定吧

l*b2013-02-03 08:02

44 楼

大家看看有没有bug, 初步试了两个好像是对的
#include
using namespace std;
bool gt (int a, int b) { return a > b; }
bool lt(int a, int b) { return a < b; }
bool eq(int a, int b) { return a == b; }
bool ge(int a, int b) { return a >= b; }
bool le(int a, int b) { return a <= b; }
int search(int A[], int N, int key, bool (*f) (int, int)) {
int dir = f(A[0], A[N-1]) ? -1 : 1; // direction of the search
int cur = (dir == 1) ? 0 : N - 1;
while(!f(A[cur], key)) {
cur += dir;
if(cur < 0 || cur > N - 1) return -1; // not found
}
return A[cur];
}
int main() {
int A[] = {1,2,3,3,5,6};
int n = sizeof(A)/sizeof(int);

int key = 4;
cout << "greater: " << search(A,n,key,gt) << endl;
cout << "less: " << search(A,n,key,lt) << endl;
cout << "equal: " << search(A,n,key,eq) << endl;
cout << "greater_equal: " << search(A,n,key,ge) << endl;
cout << "less_equal: " << search(A,n,key,le) << endl;
return 0;
}

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

: 写一个吧.

e*e2013-02-03 08:02

45 楼

这个不错，谢谢代码。

【在 l*******b 的大作中提到】

: 大家看看有没有bug, 初步试了两个好像是对的
: #include
: using namespace std;
: bool gt (int a, int b) { return a > b; }
: bool lt(int a, int b) { return a < b; }
: bool eq(int a, int b) { return a == b; }
: bool ge(int a, int b) { return a >= b; }
: bool le(int a, int b) { return a <= b; }
: int search(int A[], int N, int key, bool (*f) (int, int)) {
: int dir = f(A[0], A[N-1]) ? -1 : 1; // direction of the search

p*22013-02-03 08:02

46 楼

跟我的scala类似吧？

【在 l*******b 的大作中提到】

: 大家看看有没有bug, 初步试了两个好像是对的
: #include
: using namespace std;
: bool gt (int a, int b) { return a > b; }
: bool lt(int a, int b) { return a < b; }
: bool eq(int a, int b) { return a == b; }
: bool ge(int a, int b) { return a >= b; }
: bool le(int a, int b) { return a <= b; }
: int search(int A[], int N, int key, bool (*f) (int, int)) {
: int dir = f(A[0], A[N-1]) ? -1 : 1; // direction of the search

l*b2013-02-03 08:02

47 楼

一样的，另外看到justtry的比较头和尾的想法．结合起来写的，嗯

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

:
: 跟我的scala类似吧？

p*22013-02-03 08:02

48 楼

嗯。对。是应该结合一下。

【在 l*******b 的大作中提到】

: 一样的，另外看到justtry的比较头和尾的想法．结合起来写的，嗯

f*u2013-02-03 08:02

49 楼

这个解法太漂亮了，赏心悦目！就想找这样的解法。膜拜大牛了！

【在 l*******b 的大作中提到】

: 大家看看有没有bug, 初步试了两个好像是对的
: #include
: using namespace std;
: bool gt (int a, int b) { return a > b; }
: bool lt(int a, int b) { return a < b; }
: bool eq(int a, int b) { return a == b; }
: bool ge(int a, int b) { return a >= b; }
: bool le(int a, int b) { return a <= b; }
: int search(int A[], int N, int key, bool (*f) (int, int)) {
: int dir = f(A[0], A[N-1]) ? -1 : 1; // direction of the search

c*t2013-02-03 08:02

50 楼

赞，java怎么办，是不是只能传一个int type, 然后根据值调用gt,lt,eq....?

【在 l*******b 的大作中提到】

: 大家看看有没有bug, 初步试了两个好像是对的
: #include
: using namespace std;
: bool gt (int a, int b) { return a > b; }
: bool lt(int a, int b) { return a < b; }
: bool eq(int a, int b) { return a == b; }
: bool ge(int a, int b) { return a >= b; }
: bool le(int a, int b) { return a <= b; }
: int search(int A[], int N, int key, bool (*f) (int, int)) {
: int dir = f(A[0], A[N-1]) ? -1 : 1; // direction of the search

p*22013-02-03 08:02

51 楼

java没有函数指针吧？得用scala吧？

【在 c********t 的大作中提到】

: 赞，java怎么办，是不是只能传一个int type, 然后根据值调用gt,lt,eq....?

l*b2013-02-03 08:02

52 楼

java是不是开个interface或者class，定义一个virtual function/method 叫compare.
然后定义几个class implement这个interface或者virtual function．调用的时候调
用这些class的compare method
不懂java，不知道是不是这样用

【在 c********t 的大作中提到】

: 赞，java怎么办，是不是只能传一个int type, 然后根据值调用gt,lt,eq....?

p*22013-02-03 08:02

53 楼

compare.
感觉应该是这样的。有comparator，可以利用这个。

【在 l*******b 的大作中提到】

: java是不是开个interface或者class，定义一个virtual function/method 叫compare.
: 然后定义几个class implement这个interface或者virtual function．调用的时候调
: 用这些class的compare method
: 不懂java，不知道是不是这样用

c*t2013-02-03 08:02

54 楼

还是不会，Comparator 的 compare 返回 1，0, -1，不是boolean

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

:
: compare.
: 感觉应该是这样的。有comparator，可以利用这个。

p*22013-02-03 08:02

55 楼

可以认为0就match。

【在 c********t 的大作中提到】

: 还是不会，Comparator 的 compare 返回 1，0, -1，不是boolean

c*t2013-02-03 08:02

56 楼

嗯，可以，不过像菜鸟说的定义一个interface来代替Comparator感觉更好。然后find
method 要传入一个 Class 变量，which extends the interface,
method里要用这个Class initiate 一个instance, 再用这个instance调用compare or
f method
好像这样可以，好费劲。

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

:
: 可以认为0就match。

p*22013-02-03 08:02

57 楼

find
or
嗯。所以你应该学学scala了。java这门语言的确不咋地。C＃都强他几条街。

【在 c********t 的大作中提到】

: 嗯，可以，不过像菜鸟说的定义一个interface来代替Comparator感觉更好。然后find
: method 要传入一个 Class 变量，which extends the interface,
: method里要用这个Class initiate 一个instance, 再用这个instance调用compare or
: f method
: 好像这样可以，好费劲。

c*t2013-02-03 08:02

58 楼

是啊，等我面完了的。
俺笨鸟后飞，总是追，也追不上啊。

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

:
: find
: or
: 嗯。所以你应该学学scala了。java这门语言的确不咋地。C＃都强他几条街。

p*22013-02-03 08:02

59 楼

你面了几个了？

【在 c********t 的大作中提到】

: 是啊，等我面完了的。
: 俺笨鸟后飞，总是追，也追不上啊。

c*t2013-02-03 08:02

60 楼

唉
2个dream Fail了，2个练手也fail了，拒了一个小offer有些后悔,拒了一个onsite因为
要relocation
准备再试一个

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

:
: 你面了几个了？

s*12013-02-03 08:02

61 楼

我也贴一个，没有上面lucky的简单，不过可以改成binary search，lucky的那个应该
不好改
主要就是写了个iterator
enum FindType {
Lesser,
LesserEqual,
Equal,
GreaterEqual,
Greater
};
class Iterator {
public:
Iterator(const vector& array)
:array(array)
{
assert(array.size());
ascending = array.front() <= array.back();
offset = ascending ? 0 : array.size() - 1;
}

bool can_step(bool forward) {
int new_offset = offset + ascending == forward ? 1 : -1;
return 0 <= new_offset && new_offset < array.size();
}

Iterator& step(bool forward) {
offset += ascending == forward ? 1 : -1;
assert(valid());
return *this;
}

int operator *() { return array[offset]; }
bool valid() { return index() != -1; }
int index() { return 0 <= offset && offset < array.size() ? offset : -1;
}
private:
const vector& array;
bool ascending;
int offset;
};
Iterator find(const vector& array, int k) {
Iterator it(array);
while (it.can_step(true) && *it < k)
it.step(true);
}
int find(const vector& array, int k, FindType t) {
Iterator it = find(array, k);
if (k == *it && (t == Equal || t == LesserEqual || t == GreaterEqual))
return it.index();

if (t == Lesser || t == LesserEqual)
return *it < k ? it.index() : (it.can_step(false) ? it.step(false).
index() : -1);
if (t == Greater || t == GreaterEqual)
return *it > k ? it.index() : (it.can_step(true) ? it.step(true).
index() : -1);
return -1;
}