Binary Search problem!!

[Oxymoron]

Hi.
I've made my own Binary Search instead of using Java's because I want to return more than one item. (this does mean that its not an orthodox binary search, but nevermind).

I'm having a problem though, I wanted to be able to enter a few characters of the string i want, and it return the correct string and any other which qualify (using substring() ). I realised that sometimes the strings its looking at will be shorter than the substring length, so I included this line.
---------------------------
len = searchCriteria.length() <= arrayToSearch[pointer][0].length() ? searchCriteria.length() : arrayToSearch[pointer][0].length();
---------------------------
Where len is the endindex argument for substring (0 is the start)
Dont worry about the multidimensional array, I only ever use [pointer][0].
My problem is that sometimes substring looks at strings which are longer than its start\end index but it still throws a StringOutOfBoundsException!!

If anyone wants to have a play with it, please go ahead..I just dont understand where these exceptions are coming from.

Code:
---------------------------------------------------
package fred.BackEnd;
import java.io.*;
import fred.BackEnd.Video.Item;


public final class SearchAndSort
{
public static Item[] binarySearch(List theList,
String searchCriteria)// throws Exception
{
QuickSort sort = new QuickSort();
String[][] arrayToSearch = sort.quickSort(theList);
for (int i = 0;i < arrayToSearch.length;i++)
{
System.out.println(arrayToSearch[0] + &quot; id &quot; + arrayToSearch[1]);
}


searchCriteria = searchCriteria.toLowerCase();
int stringLen = searchCriteria.length();
//getName in Cust and Vid returns name.toLowerCase()
//Is this ok, if not can turn to lowercase in each if construct below

Item[] results = new Item[theList.getLength()];
int nextFreeLocation = 0;
int startOfArray = 0;
int pointer;
int num;
int endOfArray = (arrayToSearch.length - 1);
int len = 0;
System.out.println(&quot;\n\n\n&quot;

do
{

num = ((endOfArray - startOfArray) / 2);
pointer = (num + startOfArray);
int foundAlready = 0;
len = searchCriteria.length() <= arrayToSearch[pointer][0].length() ? searchCriteria.length() : arrayToSearch[pointer][0].length();
System.out.println(&quot;string len: &quot; + len);
System.out.println(&quot;looking at: &quot; + arrayToSearch[pointer][0]);

if (searchCriteria.compareTo(arrayToSearch[pointer][0].substring(0, len)) < 0)
{
endOfArray = (pointer - 1);
}
else if (searchCriteria.compareTo(arrayToSearch[pointer][0].substring(0, len)) > 0)
{
startOfArray = (pointer + 1);
}
else if (searchCriteria.compareTo(arrayToSearch[pointer][0].substring(0, len)) == 0)
{
int start = pointer;
while (start >= 0)
{
if (searchCriteria.compareTo(arrayToSearch[start][0].substring(0, len)) == 0)
{
results[nextFreeLocation++] = theList.getItem(Integer.parseInt(arrayToSearch[start--][1]));
}
else break;
}
start = pointer + 1;
while (start < arrayToSearch.length)
{
if (searchCriteria.compareTo(arrayToSearch[start][0].substring(0, len)) == 0)
results[nextFreeLocation++] = theList.getItem(Integer.parseInt(arrayToSearch[start++][1]));
else break;
}
break;
}

//need to find a good way of ending search safely, having found ALL results
}while (pointer != startOfArray);

System.out.println(&quot;DEBUG TEXT - SearchAndSort:59 finished loop & found &quot; + (nextFreeLocation) + &quot; matches&quot;
return results;

}

}//end of class SearchAndSort
-------------------------------------------------

Thankyou all!
Oxy

we are all of us living in the gutter.
But some of us are looking at the stars.

 

[Stijn147]

The error is in this part:


int start = pointer;
while (start >= 0)
{
if (searchCriteria.compareTo(arrayToSearch[start][0].substring(0, len)) == 0)
{
results[nextFreeLocation++] = theList.getItem(Integer.parseInt(arrayToSearch[start--][1]));
}
else break;
}


When you decrement start, start can now point to a String that is shorter then both searchCriteria and the String pointer is pointing to.

You'll have to put this before the if-statement.
len = searchCriteria.length() <= arrayToSearch[start].length() ? searchCriteria.length() : arrayToSearch[start].length();