B
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
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