主题
:
一道面试题
查看单个帖子
#
2
(
permalink
)
2007-12-06
bankrock
高级会员
注册日期: 2003-12-11
帖子: 847
文章:
7
回复: 一道面试题
这种情况下一个数组里最多只有一个断点(也就是<关系不成立的那个点)。用二分法查找,平均分割两个数组,一个是“光滑”的(<关系始终成立),另外一个和原数组最多存在一个断点。根据最后一个元素大于第一个元素,判断子数组是否光滑,然后确认要查找的数组是否在这个光滑数组里,不是的话递归查找另外一个子数组。时间复杂度O(lgn)。
bankrock
查看公开信息
发送悄悄话给 bankrock
查找 bankrock 发表的所有帖子
查看 Blog