由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Programming版 - 验证一个问题的答案
相关主题
关于 sorted and shifted 数组gdb debugging issue求助
一道c++ 题, 找出duplicate numbers请教VC2003 debug问题
An algorithm question哪位高人给个Kdevelop的小例子 (转载)
问个构造函数的问题怎么debug一个GUI program?
sigh, 不懂就不要在这里显[合集] 一个C++动态内存回收报错的问题
.NET 的环境下用C++,可是无法debug是怎么回事?debug的问题
【贴图】这个人的Emacs + GDB 是怎么做出来的? (转载)geany中怎么监控变量和设置断点?
遇到一个怪问题软断点和硬断点有什么区别啊? (转载)
相关话题的讨论汇总
话题: otherwise话题: log话题: 数组话题: check话题: array
进入Programming版参与讨论
1 (共1页)
p***o
发帖数: 44
1
不记得在哪里看到这道编程题:
一个排好序的数组,本来是可以用二分查找O(log n)找到一个数。
可是现在这个数组被切成了两半,然后前后换了一下位置。
比如:2 3 5 8 10 15 30
变成:15 30 2 3 5 8 10
切断的位置未知。在这种情况下,请找出一种办法用最快的速度找到一个数。
g*****g
发帖数: 34805
2
It's O(log n) to find the break point, so it's still
O(log n)

【在 p***o 的大作中提到】
: 不记得在哪里看到这道编程题:
: 一个排好序的数组,本来是可以用二分查找O(log n)找到一个数。
: 可是现在这个数组被切成了两半,然后前后换了一下位置。
: 比如:2 3 5 8 10 15 30
: 变成:15 30 2 3 5 8 10
: 切断的位置未知。在这种情况下,请找出一种办法用最快的速度找到一个数。

p***o
发帖数: 44
3
想了一下,不明白为啥O(log n)能找到断点

【在 g*****g 的大作中提到】
: It's O(log n) to find the break point, so it's still
: O(log n)

p***o
发帖数: 44
4
哦。你假设调换前的数组是已知的?

【在 p***o 的大作中提到】
: 想了一下,不明白为啥O(log n)能找到断点
g*****g
发帖数: 34805
5
check first and last and middle one, if they are in order,
the whole array is in order. Otherwise, check left half,
or check right half in binary fashion, I am too lazy to
think of exact algorithm, but something like that should work.

【在 p***o 的大作中提到】
: 想了一下,不明白为啥O(log n)能找到断点
c*****t
发帖数: 1879
6
Small caveat, there should be no duplicates in the array. Otherwise,
it would take O (n) with an extreme case of
original:
[ 0 1 1 ... ]
rotated:
[ 1 1 ... 0 1 ... ]

【在 g*****g 的大作中提到】
: It's O(log n) to find the break point, so it's still
: O(log n)

p***o
发帖数: 44
7
强!这些题很常见吗?呵呵

【在 c*****t 的大作中提到】
: Small caveat, there should be no duplicates in the array. Otherwise,
: it would take O (n) with an extreme case of
: original:
: [ 0 1 1 ... ]
: rotated:
: [ 1 1 ... 0 1 ... ]

1 (共1页)
进入Programming版参与讨论
相关主题
软断点和硬断点有什么区别啊? (转载)sigh, 不懂就不要在这里显
困扰多时的MATLAB crash问题.NET 的环境下用C++,可是无法debug是怎么回事?
请问在ASP.net中用Javascript的一个问题【贴图】这个人的Emacs + GDB 是怎么做出来的? (转载)
关于gdb调试c++ template的问题, 设置行号断点有offset遇到一个怪问题
关于 sorted and shifted 数组gdb debugging issue求助
一道c++ 题, 找出duplicate numbers请教VC2003 debug问题
An algorithm question哪位高人给个Kdevelop的小例子 (转载)
问个构造函数的问题怎么debug一个GUI program?
相关话题的讨论汇总
话题: otherwise话题: log话题: 数组话题: check话题: array