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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假定就是一个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 每次binary search 的iteration过程中,比较a[mid]和a[mid-1],a[mid+1]行吗?
|
f*******r 发帖数: 1086 | 4 dup不一定就出现在这3个地方吧,
需要有一个选择下一步search边界的条件,
只比较这三个元素应该不能确定边界吧。
【在 r****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 每次binary search 的iteration过程中,比较a[mid]和a[mid-1],a[mid+1]行吗?
|
r****o 发帖数: 1950 | 5 光用binary search我觉得搞不定吧,
因为duplicate可以出现在任何地方,而binary search的每一步会丢掉一半,这样可能
会把duplicate的元素丢掉。
【在 f*******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假定就是一个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 光用binary search我觉得搞不定吧, : 因为duplicate可以出现在任何地方,而binary search的每一步会丢掉一半,这样可能 : 会把duplicate的元素丢掉。
|
r****o 发帖数: 1950 | 8 Pearls好像是说找某个特定的元素,如果该元素有重复,返回第一个或最后一个。
这题是说直接找出那个重复的元素。
【在 j**l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Programming Pearls, 好像有提到如果有重复,怎么返回第一个或者是最后一个,需要 : 标准binary search的变体
|
f*******r 发帖数: 1086 | 9 恩,如果这样,问题是不一样的。
【在 r****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Pearls好像是说找某个特定的元素,如果该元素有重复,返回第一个或最后一个。 : 这题是说直接找出那个重复的元素。
|
y*c 发帖数: 904 | 10 BlueAnt gave a solution in 面试高手俱乐部
Probably he can post here also. |
|
|
s********l 发帖数: 998 | 11 恩?在哪呢?
进去找了一圈 没看到呢
【在 y*c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假定就是一个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这样不如直接顺序走一遍,本质完全一样。写起来还好看点。
|
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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你说我的么? : 我也觉的不如直接顺序走 性能方面应该还好不少 : 不过现在既然没要求性能 只要Binary search的话 只是写出来给楼主参考一下。
|
S*******n 发帖数: 1867 | 19 没offended。。
只是你的回帖里面没引言。。
我知道 我写之前就想了 觉得没啥好处。。贴出来只是给楼主参考一下
面试的时候肯定要说明先
【在 m*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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
|