f*******r
发帖数: 1086 | 1 假定就是一个int a[N]
里面是sorted的int，有一个是重复的比如
1,2,2,3,4,5
请教一下如何binary search确定这个duplicate啊？
刚才写了一下code，总是有bug，有知道的大侠请
不吝赐教！谢谢了 |
r****o
发帖数: 1950 | 2 每次binary search 的iteration过程中，比较a[mid]和a[mid-1],a[mid+1]行吗?
【在 f*******r 的大作中提到】
: 假定就是一个int a[N]
: 里面是sorted的int，有一个是重复的比如
: 1,2,2,3,4,5
: 请教一下如何binary search确定这个duplicate啊？
: 刚才写了一下code，总是有bug，有知道的大侠请
: 不吝赐教！谢谢了
|
f*******r
发帖数: 1086 | 3 我之前写了一个code:
int FindDupBSP(int a[], int left, int right)
{
while(1)
{
int mid = (left+right)/2;
int n1 = 0, n2 = 0, n3 = 0;
for(int i = left; i <= right; i++ )
{
if(a[i]
n1++;
else if(a[i] == a[mid])
n2++;
else
n3++;
【在 r****o 的大作中提到】
: 每次binary search 的iteration过程中，比较a[mid]和a[mid-1],a[mid+1]行吗?
|
f*******r
发帖数: 1086 | 4 dup不一定就出现在这3个地方吧，
需要有一个选择下一步search边界的条件，
只比较这三个元素应该不能确定边界吧。
【在 r****o 的大作中提到】
: 每次binary search 的iteration过程中，比较a[mid]和a[mid-1],a[mid+1]行吗?
|
r****o
发帖数: 1950 | 5 光用binary search我觉得搞不定吧，
因为duplicate可以出现在任何地方，而binary search的每一步会丢掉一半，这样可能
会把duplicate的元素丢掉。
【在 f*******r 的大作中提到】
: 假定就是一个int a[N]
: 里面是sorted的int，有一个是重复的比如
: 1,2,2,3,4,5
: 请教一下如何binary search确定这个duplicate啊？
: 刚才写了一下code，总是有bug，有知道的大侠请
: 不吝赐教！谢谢了
|
j**l
发帖数: 2911 | 6 Programming Pearls, 好像有提到如果有重复，怎么返回第一个或者是最后一个，需要
标准binary search的变体 |
f*******r
发帖数: 1086 | 7 呵呵，我也是在疑惑这个问题:)
不过不是很确定，努力地想了很久解决方案，
有牛人知道的能否指点一把,谢谢了！
【在 r****o 的大作中提到】
: 光用binary search我觉得搞不定吧，
: 因为duplicate可以出现在任何地方，而binary search的每一步会丢掉一半，这样可能
: 会把duplicate的元素丢掉。
|
r****o
发帖数: 1950 | 8 Pearls好像是说找某个特定的元素，如果该元素有重复，返回第一个或最后一个。
这题是说直接找出那个重复的元素。
【在 j**l 的大作中提到】
: Programming Pearls, 好像有提到如果有重复，怎么返回第一个或者是最后一个，需要
: 标准binary search的变体
|
f*******r
发帖数: 1086 | 9 恩，如果这样，问题是不一样的。
【在 r****o 的大作中提到】
: Pearls好像是说找某个特定的元素，如果该元素有重复，返回第一个或最后一个。
: 这题是说直接找出那个重复的元素。
|
y*c
发帖数: 904 | 10 BlueAnt gave a solution in 面试高手俱乐部
Probably he can post here also. |
|
|
s********l
发帖数: 998 | 11 恩？在哪呢？
进去找了一圈 没看到呢
【在 y*c 的大作中提到】
: BlueAnt gave a solution in 面试高手俱乐部
: Probably he can post here also.
|
y*c
发帖数: 904 | |
S*******n
发帖数: 1867 | |
S*******n
发帖数: 1867 | 14 C# code 如下下
调用如下：
static void Main(string[] args)
{
int[] A = { 1, 2, 3, 4, 5, 6, 7, 8,8 };
int dup = FindDuplicateByBS(A, 0, A.Count() - 1);
Console.WriteLine(dup);
Console.ReadKey();
}
public static int FindDuplicateByBS(int[] IntArray, int p, int q)
{
//Assume the array has non negative numbers.
if (p == q)
{
return -1;
}
if (p == q - 1)
{
if (IntArray[p] == IntArray[q])
{
return IntArray[p];
}
else
{
return -1;
}
}
【在 f*******r 的大作中提到】
: 假定就是一个int a[N]
: 里面是sorted的int，有一个是重复的比如
: 1,2,2,3,4,5
: 请教一下如何binary search确定这个duplicate啊？
: 刚才写了一下code，总是有bug，有知道的大侠请
: 不吝赐教！谢谢了
|
m*****g
发帖数: 226 | 15 你这样不如直接顺序走一遍，本质完全一样。写起来还好看点。 |
S*******n
发帖数: 1867 | 16 你说我的么？
我也觉的不如直接顺序走 性能方面应该还好不少
不过现在既然没要求性能 只要Binary search的话 只是写出来给楼主参考一下。
【在 m*****g 的大作中提到】
: 你这样不如直接顺序走一遍，本质完全一样。写起来还好看点。
|
y*c
发帖数: 904 | 17 binary search的话，你要知道这些数的range吧, 然后用radix sort的方法扔掉一般少
的。否则的话，我觉得需要linear time. |
m*****g
发帖数: 226 | 18 don't be offended.
but they way u write it, not really any benefit of binary search.
it is essentially the same thing as linear walking
【在 S*******n 的大作中提到】
: 你说我的么？
: 我也觉的不如直接顺序走 性能方面应该还好不少
: 不过现在既然没要求性能 只要Binary search的话 只是写出来给楼主参考一下。
|
S*******n
发帖数: 1867 | 19 没offended。。
只是你的回帖里面没引言。。
我知道 我写之前就想了 觉得没啥好处。。贴出来只是给楼主参考一下
面试的时候肯定要说明先
【在 m*****g 的大作中提到】
: don't be offended.
: but they way u write it, not really any benefit of binary search.
: it is essentially the same thing as linear walking
|
