主题: 一道面试题
查看单个帖子
  #2 (permalink)  
旧 2007-12-06
bankrock 的头像
bankrock bankrock 当前离线
高级会员
 
注册日期: 2003-12-11
帖子: 847
文章: 7
bankrock 正向着好的方向发展
默认 回复: 一道面试题

这种情况下一个数组里最多只有一个断点(也就是<关系不成立的那个点)。用二分法查找,平均分割两个数组,一个是“光滑”的(<关系始终成立),另外一个和原数组最多存在一个断点。根据最后一个元素大于第一个元素,判断子数组是否光滑,然后确认要查找的数组是否在这个光滑数组里,不是的话递归查找另外一个子数组。时间复杂度O(lgn)。
回复时引用此帖