二进制搜索类：检索有序数组中最后一个元素的小问题 [英] Binary search class: small problem retrieving the last element in the ordered array
问题描述
你好，
我有一个字符串数组，需要找到匹配的字符串和
最快的代码。我决定订购数组，然后写一个二进制的
搜索算法。
我想出的是以下内容。我注意到如果我设置：
int upper = strings.GetUpperBound（0）;
我永远不会匹配数组中的最后一个元素（即iii）
如果我设置：
int upper = strings.GetUpperBound（0）+ 1;
我也能匹配数组中的最后一个元素。
问题是我认为上层应该等于
strings.GetUpperBound（0）。
有什么我想念的吗？算法是错误的还是遗漏了什么???
使用系统;
命名空间TestApplication
{
class BinarySearchClass
{
static void Main（string [] args）
{
string [] strings = new string [] {" aaa"，" bbb"，" ccc"，" ddd"，" eee"，" fff"，
" ggg"， " hhh"，" iii"};
BinarySearchClass search = new BinarySearchClass（）;
int res = search.FindString（字符串，iii）;
Console.Read（）;
}
public int FindString （string [] strings，string str）
{
int lower = strings.GetLowerBound（0）;
int upper = strings.GetUpperBound （0）;
返回this.BinarySearch（字符串，str，lower，upper）;
}
public int BinarySearch（string [] strings，string str，int lowerbound，int
upper绑定）
{
int pos =（（上限 - 下限）/ 2）+下限;
int res = string 。比较（字符串[pos]，str）;
if（res 0）
{
pos = this.BinarySearch （strings，str，lowerbound，pos）;
}
else if（res< 0）
{
pos = this.BinarySearch（strings，str，pos，upperbound）;
}
返回pos;
}
}
}
问候，
Bob Rock
Hello,
I have an array of strings and need to find the matching one with the
fastest possible code. I decided to order the array and then write a binary
search algo.
What I came up with is the following. I noticed that if I set:
int upper = strings.GetUpperBound(0);
I never match the last element in the array (i.e. "iii")
while if I set:
int upper = strings.GetUpperBound(0) + 1;
I''m able to match also the last element in the array.
The problem is that I think upper should indeed be equal to
strings.GetUpperBound(0).
Is there something I''m missing??? Is the algo wrong or missing something???
using System;
namespace TestApplication
{
class BinarySearchClass
{
static void Main(string[] args)
{
string[] strings = new string[]{"aaa", "bbb", "ccc", "ddd", "eee", "fff",
"ggg", "hhh", "iii"};
BinarySearchClass search = new BinarySearchClass();
int res = search.FindString(strings, "iii");
Console.Read();
}
public int FindString(string[] strings, string str)
{
int lower = strings.GetLowerBound(0);
int upper = strings.GetUpperBound(0);
return this.BinarySearch(strings, str, lower, upper);
}
public int BinarySearch(string[] strings, string str, int lowerbound, int
upperbound)
{
int pos = ((upperbound - lowerbound) / 2) + lowerbound;
int res = string.Compare(strings[pos], str);
if(res 0)
{
pos = this.BinarySearch(strings, str, lowerbound, pos);
}
else if(res < 0)
{
pos = this.BinarySearch(strings, str, pos, upperbound);
}
return pos;
}
}
}
Regards,
Bob Rock
推荐答案
你需要设置upper = strings.GetUpperBound（0）+ 1.这是因为当你将
除以
除以2时，你截断并因此永远无法达到数组的结尾，
除非你添加
1.
我不明白为什么你的算法不会永远循环如果
数组中没有匹配项。你需要检查
是否新的pos不等于上限或
的下限。如果是，则二进制搜索完成，即使元素未找到
。继续
调用BinarySearch将永远计算相同的pos。
你应该*认真考虑使用.Net库的BinarySearch
而不是
写你自己的，恕我直言。
Bob Rock < ye ******************** @ hotmail.com.nospamwrote in message
新闻：O7 ******** ****** @ TK2MSFTNGP06.phx.gbl ...
You do need set upper = strings.GetUpperBound(0) + 1. This is because when
you
divide by 2, you truncate and thus can never attain the end of the array,
unless you add
1.
I don''t see why your algorithm does not loop forever if there is no match in
the array. You
should check to see that the new pos is not equal to either the upper or
lower bound. If it is, the binary search is done, even if the element is
not found. Continuing to
call BinarySearch will just calculate the same pos forever.
You should *seriously* consider using the .Net library''s BinarySearch
instead
of writing your own, IMHO.
"Bob Rock" <ye********************@hotmail.com.nospamwrote in message
news:O7**************@TK2MSFTNGP06.phx.gbl...
您好，
我有一个数组字符串，需要找到匹配的一个与
最快的代码。我决定订购数组，然后写一个
二元搜索算法。
我想出的是以下内容。我注意到如果我设置：
int upper = strings.GetUpperBound（0）;
我永远不会匹配数组中的最后一个元素（即iii）
如果我设置：
int upper = strings.GetUpperBound（0）+ 1;
我也能匹配数组中的最后一个元素。
问题是我认为上层应该等于
strings.GetUpperBound（0）。
有什么我想念的吗？算法是错误还是缺失
某事???
使用系统;
命名空间TestApplication
{
class BinarySearchClass
{
static void Main（string [] args）
{
string [] strings = new string [] {" aaa"，" bbb"，" ccc"，" ddd"，" eee"，
fff，ggg，hhh，iii};
BinarySearchClass search = new BinarySearchClass（）;
int res = search.FindString（strings，" iii"）;
Console.Read（）;
}
public int FindString（string [] strings，string str）
{
int lower = strings.GetLowerBound（0）;
int upper = strings.GetUpperBound（0）;
返回this.BinarySearch（字符串，str，lower，upper）;
} $ / $
public int BinarySearch（string [] strings，string str，int l owerbound，int
上限）
{
int pos =（（上限 - 下限）/ 2）+下限;
int res = string.Compare（strings [pos]，str）;
if（res 0）
{
pos = this.BinarySearch（strings，str，lowerbound，pos）;
}
else if（res< 0）
{
pos = this.BinarySearch（strings，str，pos，upperbound）;
}
返回pos;
}
}
}
问候，
Bob Rock
Hello,
I have an array of strings and need to find the matching one with the
fastest possible code. I decided to order the array and then write a
binary search algo.
What I came up with is the following. I noticed that if I set:
int upper = strings.GetUpperBound(0);
I never match the last element in the array (i.e. "iii")
while if I set:
int upper = strings.GetUpperBound(0) + 1;
I''m able to match also the last element in the array.
The problem is that I think upper should indeed be equal to
strings.GetUpperBound(0).
Is there something I''m missing??? Is the algo wrong or missing
something???
using System;
namespace TestApplication
{
class BinarySearchClass
{
static void Main(string[] args)
{
string[] strings = new string[]{"aaa", "bbb", "ccc", "ddd", "eee",
"fff", "ggg", "hhh", "iii"};
BinarySearchClass search = new BinarySearchClass();
int res = search.FindString(strings, "iii");
Console.Read();
}
public int FindString(string[] strings, string str)
{
int lower = strings.GetLowerBound(0);
int upper = strings.GetUpperBound(0);
return this.BinarySearch(strings, str, lower, upper);
}
public int BinarySearch(string[] strings, string str, int lowerbound, int
upperbound)
{
int pos = ((upperbound - lowerbound) / 2) + lowerbound;
int res = string.Compare(strings[pos], str);
if(res 0)
{
pos = this.BinarySearch(strings, str, lowerbound, pos);
}
else if(res < 0)
{
pos = this.BinarySearch(strings, str, pos, upperbound);
}
return pos;
}
}
}
Regards,
Bob Rock
Bob Rock写道：
Bob Rock wrote:
你好，
我有一个字符串数组，需要找到匹配的字符串和
最快的代码。我决定订购数组，然后写一个二进制的
搜索算法。
我想出的是以下内容。我注意到如果我设置：
int upper = strings.GetUpperBound（0）;
我永远不会匹配数组中的最后一个元素（即iii）
如果我设置：
int upper = strings.GetUpperBound（0）+ 1;
我也能匹配数组中的最后一个元素。
问题是我认为上层应该等于
strings.GetUpperBound（0）。
有什么我想念的吗？算法是错误的还是遗漏了什么???
使用系统;
名称空间TestApplication
{
class BinarySearchClass
{
static void Main（string [] args）
{
string [] strings = new string [] {" aaa"，" bbb"，" ccc"，" ddd"，" eee"，" fff"，
" ; ggg"，" hhh"，" iii"};
BinarySearchClass search = new BinarySearchClass（）;
int res = search.FindString（strings，" iii"）;
Console.Read（）;
}
public int FindString（string [] strings，string str）
{
int lower = strings.GetLowerBound（0）;
int upper = strings.GetUpperBound（0）;
返回this.BinarySearch（字符串，str，lower，upper）;
}
public int BinarySearch（string [] strings，string str， int lowerbound，int
upperbound）
{
int pos =（（upperbound - lowerbound）/ 2）+ lowerbound;
int res = string.Compare（strings [pos]，str）;
if（res 0）
{
pos = this.BinarySearch（strings，str，lowerbound，pos）;
}
else if（res< 0）
{
pos = this.BinarySearch（strings，str，pos，upperbound）;
}
返回pos;
}
}
}
问候，
Bob Rock
Hello,
I have an array of strings and need to find the matching one with the
fastest possible code. I decided to order the array and then write a binary
search algo.
What I came up with is the following. I noticed that if I set:
int upper = strings.GetUpperBound(0);
I never match the last element in the array (i.e. "iii")
while if I set:
int upper = strings.GetUpperBound(0) + 1;
I''m able to match also the last element in the array.
The problem is that I think upper should indeed be equal to
strings.GetUpperBound(0).
Is there something I''m missing??? Is the algo wrong or missing something???
using System;
namespace TestApplication
{
class BinarySearchClass
{
static void Main(string[] args)
{
string[] strings = new string[]{"aaa", "bbb", "ccc", "ddd", "eee", "fff",
"ggg", "hhh", "iii"};
BinarySearchClass search = new BinarySearchClass();
int res = search.FindString(strings, "iii");
Console.Read();
}
public int FindString(string[] strings, string str)
{
int lower = strings.GetLowerBound(0);
int upper = strings.GetUpperBound(0);
return this.BinarySearch(strings, str, lower, upper);
}
public int BinarySearch(string[] strings, string str, int lowerbound, int
upperbound)
{
int pos = ((upperbound - lowerbound) / 2) + lowerbound;
int res = string.Compare(strings[pos], str);
if(res 0)
{
pos = this.BinarySearch(strings, str, lowerbound, pos);
}
else if(res < 0)
{
pos = this.BinarySearch(strings, str, pos, upperbound);
}
return pos;
}
}
}
Regards,
Bob Rock
鲍勃，这个怎么样..
int pos = Array.BinarySearch< ; string>（字符串，" iii"）;
JW
Bob, how about this..
int pos= Array.BinarySearch<string>(strings, "iii");
J.W.
是的，我提供的代码执行循环永远，如果没有匹配。
我编写了我自己的算法，因为我不希望BinarySearch每次都按照数组
订购，因为它确实如此。数组已经订购。
至于搜索字符串不在数组中的停止条件，
upper == lower不保证搜索停止。
例如，如果搜索到的字符串按字典顺序大于数组中的任何其他字符串，则lower永远不会等于upper和
algo继续循环，直到堆栈溢出异常升级为止。
我想知道如何编写停止条件来处理任何情况。
Bob Rock
" Fred Mellender" < no **************** @ frontiernet.netwrote in message
news：aR ************** *** @ news02.roc.ny ...
Yes, the code as I provided it does loop forever if there is no match.
I coded my own algo because I don''t want BinarySearch to order by array
every single time, as it indeed does. The array is already ordered.
As for the stop condition when the searched string is not in the array,
upper == lower does not guarantee the search from stopping.
For example, if the searched string is lexicographically bigger than any
other string in the array, lower never gets to be equal to upper and the
algo goes on in a loop until a until a stack overflow exception is rised.
I wonder how I should write the stop condition to handle any situation.
Bob Rock
"Fred Mellender" <no****************@frontiernet.netwrote in message
news:aR*****************@news02.roc.ny...
你需要设置upper = strings.GetUpperBound（0）+ 1.这是因为
当你将
除以2时，你截断并因此永远无法达到数组的结尾，
除非你加上
1.
我不明白为什么你的算法不会永远循环如果没有匹配
在数组中。你需要检查
是否新的pos不等于上限或
的下限。如果是，则二进制搜索完成，即使元素未找到
。继续
调用BinarySearch将永远计算相同的pos。
你应该*认真考虑使用.Net库的BinarySearch
而不是写自己的
，恕我直言。
You do need set upper = strings.GetUpperBound(0) + 1. This is because
when you
divide by 2, you truncate and thus can never attain the end of the array,
unless you add
1.
I don''t see why your algorithm does not loop forever if there is no match
in the array. You
should check to see that the new pos is not equal to either the upper or
lower bound. If it is, the binary search is done, even if the element is
not found. Continuing to
call BinarySearch will just calculate the same pos forever.
You should *seriously* consider using the .Net library''s BinarySearch
instead
of writing your own, IMHO.
这篇关于二进制搜索类：检索有序数组中最后一个元素的小问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
