Solved

a search and find algorithm

Posted on 2013-01-18
9
391 Views
Last Modified: 2013-02-01
Hi there;

I have a bunch of numbers in a text file, around 80000 lines, the first ones are as follows:

1       0.9
268       5.1
46       0.17
4620       0.0
468       0.15
4631       0.15
4673       0.9
46732       1.1

What I am trying to do is finding the corresponding second column e.g. (1.1) by searching for a string e.g., 46-73-212345. I am trying to find the longest option possible meaning,
46732 will be the exact match for the input 46-73-212345, but for another string value 46-73-111134, then 4673 would be the exact match.

Since there are too many records, how can i process this in C# or Java?
This is obvious an algorithm based question.

e.g. should I go per character matching but consider the number of total records which is high..

Regards.
0
Comment
Question by:jazzIIIlove
  • 4
  • 2
  • 2
  • +1
9 Comments
 
LVL 37

Assisted Solution

by:TommySzalapski
TommySzalapski earned 167 total points
ID: 38794278
What if there is a tie?

80,000 is quite small for the computer so you could just go through the list one at a time and see how long the match is.
Since they appear to be sorted, you could use a binary search to find the closest match.
Note that if you look at where your number would fit in the sorted list, either the one right above or right below will be the longest match but there could be dozens that tie for longest match.
0
 
LVL 12

Author Comment

by:jazzIIIlove
ID: 38794328
If tie, the one encountered first is taken into account.

And yes, left column is sorted.

Regards.
0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 38794373
So you want to do something like this
string longest;
int max = 0;

foreach string s in leftcolumn
{
  match = Check how long the match is
  if (match > max)
  {
    max = match;
    longest = s;
  }
}

Note that since they are sorted, if match < max, you can quit. You'll never get a better match.

You could play around with different collections in C# or Java, but that's the basic algorithm.
You could also do a binary search for where the search string "belongs" and run up to find the first one.

Of course, you'll probably find it easiest to make a new string that has no '-' in it and use that to search.
0
 
LVL 12

Author Comment

by:jazzIIIlove
ID: 38794817
Can you guide me how i can use binary search? Any sample code for this?

Thanks.

Regards.
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 84

Accepted Solution

by:
ozo earned 167 total points
ID: 38796345
0
 
LVL 6

Expert Comment

by:yats
ID: 38796431
And yes, left column is sorted.

How the left column is sorted??
0
 
LVL 12

Author Comment

by:jazzIIIlove
ID: 38797213
left column is sorted per character:

1       0.9
268       5.1
46       0.17
4620 ...

first character is 1 in the first row.
first character is 2 in the second row.
first character is 4 in the third row.
first character is again 4 in the fourth row, second character is 6, again a tie, then 2 is coming in the fourth row.

So, look vertical alignment of numbers in that sense.

Regards.
0
 
LVL 6

Assisted Solution

by:yats
yats earned 166 total points
ID: 38797691
I thought the same at firsh place, but have a look at 5th and 6th row
468       0.15
4631       0.15

the way you explained it's not seems to be sorted.
0
 
LVL 12

Author Comment

by:jazzIIIlove
ID: 38845349
yup, good point. I sorted them in horizontal order.

Regards.
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Stream.BeginRead and Stream.EndRead in .NET Core 5 38
Two different visual studio versions 3 23
Data is not showing from images 15 38
System.Speech 2 17
Exception Handling is in the core of any application that is able to dignify its name. In this article, I'll guide you through the process of writing a DRY (Don't Repeat Yourself) Exception Handling mechanism, using Aspect Oriented Programming.
Calculating holidays and working days is a function that is often needed yet it is not one found within the Framework. This article presents one approach to building a working-day calculator for use in .NET.
Viewers learn about the “while” loop and how to utilize it correctly in Java. Additionally, viewers begin exploring how to include conditional statements within a while loop and avoid an endless loop. Define While Loop: Basic Example: Explanatio…
Viewers will learn about basic arrays, how to declare them, and how to use them. Introduction and definition: Declare an array and cover the syntax of declaring them: Initialize every index in the created array: Example/Features of a basic arr…

864 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

25 Experts available now in Live!

Get 1:1 Help Now