"Aggeboe" <XXXaggeboe@bigfoot.com> wrote in message
news:3B0BDCC2.BF782EEE@bigfoot.com...
>
> Hvis der ikke er nogen eksakt match træder de tre sidste i brug!
> De skulle så gerne sikre, at hvis man så søger på fx. "abe" og abe ikke
findes i
> array'et, så finder man istedet "abekat", hvis det nu er det første med
"abe"... Men
> det virker ikke?
Det vil jeg kalde for en partiel match i denne mail.
> Er der nogen der kan se hvorfor dette går galt?
Ja, du skal vente med at kontrollere for en partiel match til efter du har
afgjort at der ikke er en eksakt match.
Altså: Først binær søgning. Når den er slut, ved du at den søgte streng
ikke er i arrayet. Og så kikker du efter om den plads din søgning endte
ved, er et partielt match.
Du kan se hvordan i nedenstående kode.
---
Steffen Enni
http://www.zachosw.dk
public class Search
{
public String search(String x, String arr[]) {
int n = arr.length;
int a = 0;
int b = n - 1;
while (a <= b) {
file://Invariant: arr[a] ... <=b" + i + "b" + i + " x <= ... arr[b]
int i = (a+b)/2;
int cmp = x.compareTo(arr[i]);
if (cmp < 0) {
b = i - 1;
} else if (cmp > 0) {
a = i + 1;
} else {
return arr[i];
}
}
file://Invariant: a == b+1 hvilket betyder, at
file://man kan være løbet ovenud af arrayet.
file://Ellers check om x er præfix til arr[a]
if (a > (n-1)) {
return null;
} else if (arr[a].startsWith(x)) {
return arr[a];
} else {
return null;
}
}
file://Test driver
public static void main(String args[]) {
String array[] = new String[9];
for(int i = 0; i < array.length; i++)
array[i] = "b" + i + "b";
boolean passed = true;
for(int j = 1; j < array.length; j++) {
passed &= test(array, j);
}
System.out.println(passed ? "OK" : "FAILED");
}
private static boolean test(String arr[], int len) {
String array[] = new String[len];
System.arraycopy(arr, 0, array, 0, len);
Search test = new Search();
boolean passed = true;
for(int i = 0; i < array.length; i++) {
String x = "";
String y = "";
try {
y = "a";
x = test.search(y, array);
if (x != null) {
System.out.println("Bummer: " + y + ", " + x);
passed = false;
}
y = "b" + i;
x = test.search(y, array);
if (!x.equals("b"+i+"b")) {
System.out.println("Bummer: " + y + ", " + x);
passed = false;
}
y = "b" + i;
x = test.search(y, array);
if (!x.equals("b"+i+"b")) {
System.out.println("Bummer: " + y + ", " + x);
passed = false;
}
y = "b" + i + "b";
x = test.search(y, array);
if (!x.equals("b"+i+"b")) {
System.out.println("Bummer: " + y + ", " + x);
passed = false;
}
y = "b" + i + "c";
x = test.search(y, array);
if (x != null) {
System.out.println("Bummer: " + y + ", " + x);
passed = false;
}
y = "c";
x = test.search(y, array);
if (x != null) {
System.out.println("Bummer: " + y + ", " + x);
passed = false;
}
} catch (NullPointerException e) {
System.out.println("Bummer " + y + ", null");
passed = false;
}
}
return passed;
}
}