Binary Search with Strings

Question

I have an object array and I want to search the date / day property (user decides) by using binary search.

**EDIT: I read the SharesArray[mid].Date values (and day values) from a text file and examples are: 05/02/2015, 14/10/2014.The searchString value would be gained from the user but would be in the same format as the date values. **

This is my first attempt so I am just trying the date property:

int high, low, mid;
high = SharesArray.Length - 1;
low = 0;

while (low <= high)
{
    mid = (low + high) / 2;
    if (String.Compare(SharesArray[mid].Date, searchString, true) == 0)
    {
        break;
    }
    else if (String.Compare(SharesArray[mid].Date, searchString, true) > 0)
    {
        high = mid - 1;
    }
    else if (String.Compare(SharesArray[mid].Date, searchString, true) < 0)
    {
        low = mid + 1;
    }

I have also tried the last else if statement as just else and that doesn't make any difference.

Also, does it matter what way round string1 and string2 are in the String.Compare part?

Could you please show us how Date is defined in SharesArray and give us an example of what value searchString could be and what possible values SharesArray[mid].Date could be? — John Odom
– John Odom, Commented Apr 9, 2015 at 21:41
I thought so too but when I used a breakpoint and watched the flow of control it went to different elements in my array when I swapped them. — GratefulDemon
– GratefulDemon, Commented Apr 9, 2015 at 21:41
@Steve The order in the Compare call is most definitely not irrelevant and the mid calculation is correct, although it is potentially vulnerable to an overflow, so mid = low + ((high - low) >> 1) would be better — Alex
– Alex, Commented Apr 9, 2015 at 21:51

Alex · Accepted Answer · 2015-04-10 20:10:05Z

1

Summarizing an answer from the Q&A in the comments of the question, with a bit of additional context.

For binary search, there are a few ingredients you need to take care of

The input array to the binary search function must be sorted.
Given the algorithm you have implemented, they must be sorted in ascending order.
You must have a three-way comparison function, that for compare(lhs, rhs) returns: < 0 if lhs < rhs, > 0 if lhs > rhs and 0 if lhs == rhs.
The order of the arguments in the compare function matters, if you switch them, you will be taking the wrong branch and changing the upper search bound instead of the lower, or the other way around.
For your implementation, you had the order correct, with lhs : SharesArray[mid].Date and rhs = searchString.
Because you are comparing dates, you need to use the DateTime.Compare function, and convert your date strings to DateTime instances, using DateTime.ParseExact(myString, "dd/MM/yyyy", CultureInfo.InvariantCulture);. With a string comparison you would get wrong results such as "05/02/2015" < "14/10/2014".

And then there is one more anecdotal remark to make (see here):

The calculation of the pivot value mid is susceptible to integer overflow. If you calculate it as

mid = (low + high) / 2;

then low + high could become larger than fits in an integer.

The preferred way of calculating mid is therefore

`mid = low + ((high - low) >> 1);`.

edited Apr 10, 2015 at 20:10

answered Apr 10, 2015 at 1:59

Alex

13.3k36 silver badges62 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

PiotrWolkowski Over a year ago

@EmmaD Since Alex's answer from the comments worked for you probably, for the benefit of the future generations, it's worth to accept this summary as an answer.

Jason · Accepted Answer · 2015-04-09 21:59:05Z

0

Have you considered LINQ?

var searchIndex = SharesArray
    .Select(s => s.Date)
    .ToList()
    .BinarySearch(searchString);

answered Apr 9, 2015 at 21:59

Jason

5273 silver badges14 bronze badges

2 Comments

GratefulDemon Over a year ago

I am trying not to use the BinarySearch in built method

Mephy Over a year ago

@EmmaD anything you're trying to achieve should be mentioned in the question.

Collectives™ on Stack Overflow

Binary Search with Strings

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related