Binary Search

Binary Search

Binary Search är en algoritm för att leta efter ett visst nummer i en sorterad array.
Tänk dig att det finns en lista med x antal nummer där du ska gissa vilket nummer av alla i listan som är det rätta numret.. Det enda svar du kan få, när du gissar vilket nummer det är, är om det är högre än eller lägre än din gissning.  Binary search är ett exempel på hur du kan optimera den här sortens sökning. Det bästa är att först gissa på det nummer som ligger i mitten på listan. Då kan du eliminera halva listan när du får veta om “rätt” tal är högre eller lägre än din gissning. Om halvering fortsätter så kommer rätt tal att hittas väldigt snabbt.
Anta att listan har 100 000 tal. Om du bara skulle gissa utan att ha ett system så skulle antal gissningar i värsta fall bli 100 000 st . Om du istället använder binary search skulle antalet gissningar kunna bli väldigt mycket färre.

 Kan du räkna ut max antal gissningar om binary search används på 100 000 tal?

Ett program ska skapas som visar på canvasen hur Binary Search går till

Först i programmet skapas sex variabler. Efter varje variabel står en beskrivning av vad variabeln är. Här väljer vi att skriva förklaringen på engelska då det är bra att träna på att använda engelskan när man programmerar. Nästan alla webbsidor som finns med tutorials och forum för frågor är på engelska.

var nums = [];//array to keep all numbers
var start;//begining of array
var stop; //end of array
var middle;// mid number in array
var value; //number to search for
var count = 1;//how many times before number is found. 
//count is set to start at one because the program picks middle number when starts

Arrayen nums börjar som en tom array då vi senare ska slumpa värden till den.
Variabeln count börjar på 1 eftersom programmet kommer att “gissa” ett nummer direkt när det startas.
Övriga variabler initieras utan värden. Att de initieras  globalt (utanför någon funktion) gör att de kan användas överallt i programmet.

I setup() skapas en canvas med storlek 500 * 400 pixlar.
En for-loop används för att fylla arrayen nums med tjugo heltal mellan 0 och 49 (från 0, upp till men inte inkluderat 50).
Variabeln value sätts till ett slumpmässigt valt nummer av numren i arrayen.
Sist sorteras innehållet i num i nummerordning

function setup() {
  createCanvas(500, 400);
  //populate array with 20 numbers between 0 and 50
  for (var i = 0; i < 20; i++) {
    nums.push(floor(random(0, 50)));
    //picking one number out of array to search for
    value = floor(random(nums));
  }
  //sorting the array in order
  nums.sort(function(a, b) {
    return a - b
  });
}

Om du loggar num och value till konsollen innan sista avslutande klammerparentesen ser du vilka tal som valts.

console.log(nums);
console.log(value);

Skapa kod i draw() som visar text på canvasen .

Värden för variablerna start och stop bestäms också här.
Om du funderar över koden för text (textAlign) eller annan så kan du titta på referenserna i p5.js

Sista if-satsen säger att om value är lika med middle så ska loopen stoppas och text ska skrivas ut.

noLoop() stoppar draw(9 från att köras om igen. Detta görs för att count inte ska kunna bli större än värdet för när “rätt tal” hittats.

function draw() {
  background(254, 215, 0);

  for (var j = 0; j < nums.length; j++) {
    textSize(14);
    text(nums[j] + ', ', 25 * j + 20, 250);
  }
textAlign(CENTER, CENTER);
textStyle(BOLD);
textSize(42);
text('BINARY SEARCH', width / 2, 50);
textSize(24);
text('searching for ' + value, width / 2, 100);
//setting the new values for start, stop and middle 
start = 0
stop = nums.length - 1
middle = floor((start + stop) / 2)
text('middle number is ' + nums[middle], width / 2, 150);
textSize(16);
text('if numbers are even\, middle number is left of middle', width / 2, 180);
textSize(42);
text('count ' + count, width/2, 360);
//if search is done, stop the loop and show text
  if (value == nums[middle]) {
    noLoop();
    textSize(24);
    textStyle(ITALIC);
    text('Middle number and searched number match!!!!', width / 2, 300);
  }
}

Skapa funktionen mousePresed() där beräkningar görs och delar av arrayen tas bort.

Nu skapas en funktion som beräknar mittersta talet  i arrayen (middle), ökar count med ett för varje musklick.
En if-sats säger att Om middle INTE( ! ) är lika med value och om start är mindre än stop

if (nums[middle] !== value && start < stop) {

Då ska nästa if-sats kollas. Om value är mindre än middle

 if (value < nums[middle]) {

Om båda dessa if-satser är true ska den del av arrayen som går från mitten till slutet av arrayen tas bort och värdet för stop ska vara middle minus 1

nums.splice(middle, nums.length);
stop = middle - 1;

Om if-satserna är false ska en else-if sats kontrolleras.

Om value är större än middle ska den första halvan av arrayen tas bort och start får värdet av middle+1

 else if (value > nums[middle]) {
  //delete half of array not containing searched value
  nums.splice(0, middle + 1);
  start = middle + 1;
}

Nedan ser du hela koden i funktionen mousePressed()

function mousePressed() {
  middle = floor((start + stop) / 2);
  //increase count for every search
  count++;
  if (nums[middle] !== value && start < stop) {
    if (value < nums[middle]) {
      //delete half of array not containing searched value
      nums.splice(middle, nums.length);
      stop = middle - 1;

  } else if (value > nums[middle]) {
    //delete half of array not containing searched value
    nums.splice(0, middle + 1);
    start = middle + 1;
  } 
  }
}

Hela koden i editor kan du se här

För att bedöma hur bra din kod är finns ett sätt att beräkna hur snabb koden är vid stora beräkningar. Det här kallas Big O Notation. 

 Läs på mer om Big O Notations genom att googla.
Länk till ett bra CheatSheet .