• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Need help with search algorithm

 
Ranch Hand
Posts: 237
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Guys,

I need a little help refining my search algorithm which involves the standard binary search. I'll begin by providing you with a sample of the data coming from a database lookup:

...
6 | 1 | Printer |
7 | 3 | Desktop |
7 | 6 | Accounts |
7 | 1 | Printer |
8 | 1 | Printer |
8 | 3 | Desktop |
9 | 1 | Printer | <<<< index 19 - first scan
9 | 5 | Web-site |
9 | 2 | Servers | <<<< index 21 - found on second scan
10 | 3 | Desktop |
10 | 1 | Printer |
11 | 3 | Desktop |
11 | 1 | Printer |
12 | 3 | Desktop |
12 | 6 | Accounts |
13 | 6 | Accounts |
13 | 3 | Desktop |
...

The first column of data is an employee id value. You'll notice that an employee id can appear more than once in this lookup. This means that when I perform a search for all records pertaining to employee number 9, let us say, I want to store the details of those records in a LinkedHashMap.
So basically my algorithm goes like so:

1. Perform a binary search for the first record that matches employee id = 9.
2. Perform more binary searches on either side of the found record. You can think of this as searching to the left and then to the right of the found record for more matches.

The method performing all this work looks like this:



When I run this on id = 9 I get the following printout to the console:

id: 9 index: 19
right side - id: 9 lowerBound: 20 l: 21
right side - id: 9 lowerBound: 21 l: 21

Records 19,20, and 21 are what I want to be loaded into the LinkedHashMap, but that is not what I get. What I get is record 19 loaded once and record 21 being loaded twice into the LinkedHashMap. Record 20 gets ignored.
I can't quite wrap my head around this one. I think something needs to change with the following lines but I'm not quite sure:

if(lowerBound == l)
{
if(l + 1) < data.length - 1)
lowerBound = l + 1;
}
else
lowerBound = l;

If it helps at all, here is my binary search method, which I'm confident is written properly. I read an article by Josh Block that covers a bug in the binary search algorithm, which I've fixed according to the article:
http://googleresearch.blogspot.ca/2006/06/extra-extra-read-all-about-it-nearly.html



So, basically my algorithm isn't finding all the records it needs to. It ignores record 20, which it should load into the LinkedHashMap, and instead it loads record 21 twice. Please advise.

Alan
 
Rancher
Posts: 1044
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Binary is applicable if the elements are sorted, which appears to be the case here.

So after having found an element with the given id I would not search any longer but would simply check the neighbors (the adjacent elements with lower and higher indices) for the same id.
 
Alan Shiers
Ranch Hand
Posts: 237
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Do you mean perform an linear search left and right with a loop structure. After I posted this, I was thinking the same thing, but at the same time, I didn't want to slow down the timing. I was thinking that using binary search left and right would maintain the timing especially on a large data set, Yes? No?

Alan
 
Ivan Jozsef Balazs
Rancher
Posts: 1044
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
No. If you found a record with the given id, then the others (if available) must be its neighbours - there is no need to search for them, you know where to check them.
 
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I agree with Ivan. Once you get the record having the input id, then you can go simply iterate backword and forward and insert data into LinkedHashMap until you get a different Id.
The modified algo should be

1. Perform a binary search for the first record that matches employee id = 9. Call it resultIndex. Insert this record into LinkedHashMap
2. Iterate over records by decrementing the index value and insert records into LinkedHashMap, until you get an Id != input Id.
3. Now set current Index = resulIndex. Iterate over records by incrementing the index value and insert records into LinkedHashMap, until you get an Id != input Id.

 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic