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