主题: 一道面试题
查看单个帖子
  #4 (permalink)  
旧 2008-04-14
polyrandom 的头像
polyrandom polyrandom 当前离线
超级版主
 
注册日期: 2002-09-03
帖子: 3,138
文章: 20
polyrandom 正向着好的方向发展
默认 回复: 一道面试题

引用:
作者: corelito 查看帖子
为什么要用二份法呢,直接遍历数组不行?设置两个指针,一前一后进行遍历。。。
因为这样做的复杂度是O(n),二分法的复杂度是O(lg n)。如果我们要的只是O(n),那还用两个指针干嘛?一个就行了,直接忽略这个数组的任何排序性质。
回复时引用此帖