出算法题啦

有一条路长4000米，取一端为起点，坐标为0，在这条路上会种一些绿化树（假设种60颗吧），任意两颗树的间隔距离是随机的，每棵树都有一个坐标，假设树的坐标范围假设为[0,4000]之间的整数。
问题是：现在随机给出一个[0,4000]之间的一个整数，请找出离这个数字最近的树的编号。
这个问题有很多解法，我想能不能给出一个解法，根据给定的整数，一下子就确定位于这个整数两端的树，然后再比较谁近。

建个逆向的映射表就可以了

建个对象
PreAndNext{
int pre;
int next;
}

PreAndNextOfLoc[4000]

典型的用空间换时间的做法.

不过这空间也浪费太多了.有很多冗余数据.

60棵数硬给整个4000的数组.

给个二分检索方法的伪代码: [code] int a[60]; int find_min_distance(int num){ int min = 0, max=60; int mid; while(true){ mid = (min+max)/2; if(mid+1 >= 60) return num - a[60]; if(mid-1 <= 0 ) return a[0] - num; if(a[mid] < num && a[mid+1] > num) return min(a[mid+1]-num,num-a[mid]); else if(a[mid] > num && a[mid-1] < num) return min(a[mid]-num,num-a[mid- 1]); else if(a[mid] > num) max = mid; else if(a[mid] < num) min = mid; } } [/code]

60棵数+位置信息一共61个数排序

可以找到该位置前一个跟后一个点,比较一次就可以了
nlog(n)的复杂度吧

现在的学生真坏，把老师出的题目装作研究技术让别人做。