Re: Binary search class: small problem retrieving the last element in the ordered array

Bob Rock wrote:
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, how about this..

int pos= Array.BinarySearch<string>(strings, "iii");

J.W.
.

Relevant Pages

  • Re: invalid lvalue in assignment
    ... it's supposed to be an array of strings, ... there's no way of associating nrows and ncolumns with that. ... void choparray(char **s, int nrows, int ncolumns); ...
    (comp.lang.c)
  • passing an array of LPSTR to C++ by reference
    ... I have written a VB program that passes an array of strings to a C++ ... The c++ dll is supposed to fill the array of strings with the ... GetJobIds(LPSTR & strReturnedJobId, int ...
    (comp.lang.cpp)
  • Re: simple array question
    ... I am trying to pass a function an array of strings, ... int smallest; ... void s38sort(e_type *array, size_t nmemb) ...
    (comp.lang.c)
  • Re: Class Memory Usage
    ... And outside of the class store the location of the data I want to ... myArray => double array, start pos 5, len 3 ... If my record is only to store a single int value (i.e. pos 0 of the ...
    (microsoft.public.dotnet.languages.csharp)
  • Binary search class: small problem retrieving the last element in the ordered array
    ... I have an array of strings and need to find the matching one with the ... public int FindString ... pos = this.BinarySearch; ...
    (microsoft.public.dotnet.languages.csharp)
Loading