b******v
发帖数: 1493 | 1 面试官是位华人，非常nice，问的题目也不难
不过我又没答好，一道在circular sorted array里binary search的题目，
当时一着急，大脑一片空白。
挂了电话，几分钟内就有了思路。
唉，看来这次又黄了。 |
r****o
发帖数: 1950 | 2 我每次电面的时候也是很紧张，一挂电话就有思路。
【在 b******v 的大作中提到】
: 面试官是位华人，非常nice，问的题目也不难
: 不过我又没答好，一道在circular sorted array里binary search的题目，
: 当时一着急，大脑一片空白。
: 挂了电话，几分钟内就有了思路。
: 唉，看来这次又黄了。
|
X**********g
发帖数: 480 | 3 我也这样， 呵呵。
面的时候 好像基本脑子就不转了 |
j**l
发帖数: 2911 | 4 可以预处理circular sorted array, 在适当位置断开使得它成为regular sorted
array么？
【在 b******v 的大作中提到】
: 面试官是位华人，非常nice，问的题目也不难
: 不过我又没答好，一道在circular sorted array里binary search的题目，
: 当时一着急，大脑一片空白。
: 挂了电话，几分钟内就有了思路。
: 唉，看来这次又黄了。
|
r****o
发帖数: 1950 | 5 分两段binary search?
【在 j**l 的大作中提到】
: 可以预处理circular sorted array, 在适当位置断开使得它成为regular sorted
: array么？
|
j**l
发帖数: 2911 | 6 或者不用断开，搞个下标映射也可
【在 r****o 的大作中提到】
: 分两段binary search?
|
b******v
发帖数: 1493 | 7 那样是O(n)，和直接遍历数组是一样的
我的hint是binary search时，除了用中点的信息，也用起点和终点的信息
【在 j**l 的大作中提到】
: 可以预处理circular sorted array, 在适当位置断开使得它成为regular sorted
: array么？
|
b******v
发帖数: 1493 | 8 我明白了，你说的预处理的目的是假如有很多次查询操作，
预处理后就可以归结为普通的binary search，速度很快
【在 j**l 的大作中提到】
: 可以预处理circular sorted array, 在适当位置断开使得它成为regular sorted
: array么？
|
r****o
发帖数: 1950 | 9 就用binary search就可以了把，分情况讨论。
不过如果存在相同元素的话，可能要要线性查找。
【在 j**l 的大作中提到】
: 或者不用断开，搞个下标映射也可
|
j**l
发帖数: 2911 | 10 这种O(n)的预处理不允许么？以后每次都可以log(n)查找了
比如原来数组A的元素是
3->4->5->6->1->2
下标映射为
new_i = (old_i + 2) % 6
old_i = (new_i + 4) % 6
这样可以得到假想的常规排序数组B
B[i] = A[(i+4)%6]
对B进行二分查找就可以了
【在 b******v 的大作中提到】
: 那样是O(n)，和直接遍历数组是一样的
: 我的hint是binary search时，除了用中点的信息，也用起点和终点的信息
|
|
|
s*********t
发帖数: 1663 | 11 binary search，肯定找着了啊，为什么空白，可惜
【在 b******v 的大作中提到】
: 面试官是位华人，非常nice，问的题目也不难
: 不过我又没答好，一道在circular sorted array里binary search的题目，
: 当时一着急，大脑一片空白。
: 挂了电话，几分钟内就有了思路。
: 唉，看来这次又黄了。
|
b******v
发帖数: 1493 | 12 当时面试一紧张，加上看起来似乎有很多情况要考虑，大脑就空白了
感觉面试时容易紧张，碰到没做过的题，很难静下心来分析算法
【在 s*********t 的大作中提到】
: binary search，肯定找着了啊，为什么空白，可惜
|
b******v
发帖数: 1493 | 13 是很可惜
还好面试官很nice，让我在面试后一小时内把程序写出来发过去
我搞定了，希望能有一点补救的效果
【在 s*********t 的大作中提到】
: binary search，肯定找着了啊，为什么空白，可惜
|
r****o
发帖数: 1950 | 14 Bless!
【在 b******v 的大作中提到】
: 是很可惜
: 还好面试官很nice，让我在面试后一小时内把程序写出来发过去
: 我搞定了，希望能有一点补救的效果
|
b******v
发帖数: 1493 | 15 多谢！
【在 r****o 的大作中提到】
: Bless!
|
s*********t
发帖数: 1663 | 16 BLESS TOO!
【在 r****o 的大作中提到】
: Bless!
|
b******v
发帖数: 1493 | 17 THANKS!
【在 s*********t 的大作中提到】
: BLESS TOO!
|
j**l
发帖数: 2911 | 18 可以这样写么？
假定当前搜索区间开始的下标是s, 中点的下标是m, 结束的下标是e,
要查找的数是x，可以证明A[s] <= A[m]和A[m] <= A[e]至少有一个成立
if (s > e)
查找失败返回;
m = (s + e) / 2;
if (x == A[m] || x == A[s] || x == A[e])
查找成功返回;
if (A[s] <= A[m])
{
if (x > A[s] && x < A[m]
在区间[s, m-1]继续找
else
在区间[m+1, e]继续找
}
else if (A[m] <= A[e])
{
if (x > A[m] && x < A[e]
在区间[m+1, e]继续找
else
在区间[s, m-1]继续找
}
else
{
// This is not possible if the original array is circular sorted
}
【在 b******v 的大作中提到】
: 是很可惜
: 还好面试官很nice，让我在面试后一小时内把程序写出来发过去
: 我搞定了，希望能有一点补救的效果
|
r****o
发帖数: 1950 | 19 如果没有重复元素应该可以，有重复元素的话，就有问题。
【在 j**l 的大作中提到】
: 可以这样写么？
: 假定当前搜索区间开始的下标是s, 中点的下标是m, 结束的下标是e,
: 要查找的数是x，可以证明A[s] <= A[m]和A[m] <= A[e]至少有一个成立
: if (s > e)
: 查找失败返回;
: m = (s + e) / 2;
: if (x == A[m] || x == A[s] || x == A[e])
: 查找成功返回;
: if (A[s] <= A[m])
: {
|
b******v
发帖数: 1493 | 20 差不多就是这样
【在 j**l 的大作中提到】
: 可以这样写么？
: 假定当前搜索区间开始的下标是s, 中点的下标是m, 结束的下标是e,
: 要查找的数是x，可以证明A[s] <= A[m]和A[m] <= A[e]至少有一个成立
: if (s > e)
: 查找失败返回;
: m = (s + e) / 2;
: if (x == A[m] || x == A[s] || x == A[e])
: 查找成功返回;
: if (A[s] <= A[m])
: {
|
|
|
j**l
发帖数: 2911 | 21 能否举例说明？
【在 r****o 的大作中提到】
: 如果没有重复元素应该可以，有重复元素的话，就有问题。
|
r****o
发帖数: 1950 | 22 22222212
找1
【在 j**l 的大作中提到】
: 能否举例说明？
|
d**e
发帖数: 6098 | 23 那有没有好的方法可以解救一下？
【在 r****o 的大作中提到】
: 22222212
: 找1
|
r****o
发帖数: 1950 | 24 我觉得在这种情况下只能线性查找，不知道谁有好的建议。
【在 d**e 的大作中提到】
: 那有没有好的方法可以解救一下？
|
j**l
发帖数: 2911 | 25 恩，对21222找1也不行
有什么改进方法么？
【在 r****o 的大作中提到】
: 22222212
: 找1
|
n******r
发帖数: 1247 | 26 会越来越有经验的，bless
【在 b******v 的大作中提到】
: 面试官是位华人，非常nice，问的题目也不难
: 不过我又没答好，一道在circular sorted array里binary search的题目，
: 当时一着急，大脑一片空白。
: 挂了电话，几分钟内就有了思路。
: 唉，看来这次又黄了。
|
j**l
发帖数: 2911 | 27 如果允许O(n)预处理的话，就可以找到分割点，通过下标映射化归为在普通有序数组中
的二分查找问题了。但这可能不是面试官想要的
【在 r****o 的大作中提到】
: 我觉得在这种情况下只能线性查找，不知道谁有好的建议。
|
b******v
发帖数: 1493 | 28 多谢！
【在 n******r 的大作中提到】
: 会越来越有经验的，bless
|
h*****l
发帖数: 46 | 29 找分割点是O(logn).
【在 j**l 的大作中提到】
: 如果允许O(n)预处理的话，就可以找到分割点，通过下标映射化归为在普通有序数组中
: 的二分查找问题了。但这可能不是面试官想要的
|
y*c
发帖数: 904 | 30 这道题，如果没有编过，电面写出正确code是很有难度的。我用两种方法编过，一种就
是jntl说的根据x[lowerbound], x[upperbound]和x[middle]跟要寻找的target做比较
，分情况进行判断，很subtle。另一种就是找出最大值（类似于找first occurrence
in a sorted array），然后找到递增的subsequence进行binary search，都是log n |
|
|
g**e
发帖数: 6127 | 31 有重复数字的时候就不好找了
complexity O（logN），和普通的binary search一样的。 |
K******g
发帖数: 1870 | 32 我修改了一下代码，现在可以了。
我已经测试过222222222122，的例子了，可以找到1.
int searchInShiftedSortedArray(int array[], int left, int right, int value)
{
if(left>right) return -1;
int is_found = -1;
int mid = (left+right)/2;
if(value == array[mid]) return mid;
if(array[mid]<=array[left])
{
if(value > array[mid] && value <= array[right])
{
is_found = BinarySearch(array, mid+1,right,value);
}
else
{
is_found = searchInShiftedSortedArray(ar
【在 g**e 的大作中提到】
: 有重复数字的时候就不好找了
:
: complexity O（logN），和普通的binary search一样的。
|
