grosse arrays schnell durchsuchen

[molily]

Hallo,

Wie sieht denn eine binäre Suche mit Javascript aus?

Ich habe keine Informatikausbildung, aber ich denke einmal, in etwa so:

var array = new Array();  
for (var i = 0, random; i < 1000; i++) {  
 random = Math.random()  
 array.push(random);  
}  
array.sort();  
//document.write("<p>" + array.join("<br>") + "</p>");  
  
suchwert = random;  
document.write("<p>suchwert: " + suchwert + "</p>");  
  
function suche (array, suchwert, index_start, index_end) {  
 index_start = index_start || 0;  
 index_end = index_end || array.length;  
  
 document.write("<p>suche " + index_start + "-" + index_end + "<br>");  
  
 index_mitte = Math.floor(index_start + ((index_end - index_start) / 2));  
 document.write("mitte: " + index_mitte + " : " +  array[index_mitte] + "<br>");  
 if (array[index_mitte] == suchwert) {  
  document.write("gefunden");  
  return true;  
 }  
 if (suchwert < array[index_mitte]) {  
  document.write("suchwert kleiner<br>");  
  return suche(array, suchwert, index_start, index_mitte);  
 } else {  
  document.write("suchwert größer<br>");  
  return suche(array, suchwert, index_mitte, index_end);  
 }  
 return false;  
}  
  
document.write("<p>" + suche(array, suchwert) + "</p>");

Das ist natürlich, wenn man einen geordneten Array hat, viel schneller als das bloße Durchlaufen mit einer for-Schleife.

Mathias