这个二进制搜索是否正确 [英] Is this binary search correct

问题描述

如果有什么问题，请你指出（如果你还是b $ b也可以给我一个例子）


int find（int array []，int size，int key）

{

int begin = 0，end = size-1，middle;

while（结束>开始）{


middle =（开始+结束）/ 2;

if（key> array [middle]）

begin = mid + 1;

else

end = middle;

}


if（key == array [end]）return end;

return -1;

}

解决方案

Kiko Tores写道：

如果有什么问题，请你指出（如果你能给我一个例子）

int find（int array []，int size，int key）
{
int begin = 0，end = size-1，middle;
while（end> begin）{< br =>
中=（开始+结束）/ 2;
if（key> array [middle]）
begin = middle + 1;
else


如果添加相等比较，你可以缩短搜索范围


if（key == array [middle]）

return middle; < br $> b $ b其他


但不一定如此，因为时间花在比较上。所以，它b / b $ b $将取决于''数组''的内容。如果平均而言_does_具有你正在寻找的价值，那么可能添加==会有所帮助。如果

它没有，它会稍微延迟决定。

end = middle;
}

if（key = = array [end]）return end;

返回-1;
}

V

但是循环无法无限正确。这就是我的教授告诉我们什么

i

Victor Bazarov写道：

Kiko Tores写道：

如果有的话是不对的，请你指出来（如果
你也可以给我一个例子）

int find（int array []，int size，int key）
{
int begin = 0，end = size-1，middle;
while（end> begin）{

middle =（begin + end）/ 2;
if（key> array [middle]）
begin = middle + 1;

如果添加相等性，你可能会缩短你的搜索范围

比较
if（key == array [middle]）
return middle;


但不一定是因为花时间比较一下。所以，
它将取决于''数组''的内容。如果平均而言_does_
具有您正在寻找的价值，那么可能添加==将有所帮助。
如果没有，它会稍微延迟决定。

end = middle;
}
if（key = = array [end]）return end;

返回-1;
}

V

>但是没有办法让循环无限正确。那是什么

我的教授告诉我

我发现你的代码没有问题（除了大小< = 0，它是

undefined）。也许你的教授可以在这里张贴一个反例：）


- Stephan

If there is something wrong , could you please point it out ( if you
can give me an example as well)

int find( int array[], int size, int key )
{
int begin=0, end=size-1, middle;
while (end>begin){

middle = (begin+end) /2;
if (key>array[middle])
begin=middle+1;
else
end = middle;
}

if (key==array[end]) return end;
return -1;
}

解决方案

Kiko Tores wrote:

If there is something wrong , could you please point it out ( if you
can give me an example as well)

int find( int array[], int size, int key )
{
int begin=0, end=size-1, middle;
while (end>begin){

middle = (begin+end) /2;
if (key>array[middle])
begin=middle+1;
else
You could probably shorten your search if you add the equality comparison

if (key == array[middle])
return middle;
else

but it''s not necessarily so because time is spent comparing too. So, it
will depend on the contents of the ''array''. If on average it _does_ have
the value you''re looking for, then probably adding the == will help. If
it does not, it will delay the decision a bit.
end = middle;
}

if (key==array[end]) return end;
return -1;
}

V

but there is no way the loop is gonna be infinite right. cuz thats what
i was told by my professor
Victor Bazarov wrote:

Kiko Tores wrote:

If there is something wrong , could you please point it out ( if you can give me an example as well)

int find( int array[], int size, int key )
{
int begin=0, end=size-1, middle;
while (end>begin){

middle = (begin+end) /2;
if (key>array[middle])
begin=middle+1;
else
You could probably shorten your search if you add the equality

comparison
if (key == array[middle])
return middle;
else

but it''s not necessarily so because time is spent comparing too. So, it will depend on the contents of the ''array''. If on average it _does_ have the value you''re looking for, then probably adding the == will help. If it does not, it will delay the decision a bit.

end = middle;
}

if (key==array[end]) return end;
return -1;
}

V

> but there is no way the loop is gonna be infinite right. cuz thats what

i was told by my professor

I see no problem with your code (except that for size<=0 it is
undefined). Maybe your prof can post a counter-example here ;)

- Stephan

这篇关于这个二进制搜索是否正确的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！