Binärer Suchalgorithmus - wo liegt der Fehler?

Hallo liebe Community,

ich arbeite an einem Suchalgorithmus, der in einer sortierten Liste das Element finden soll, das einem gegebenen Wert am nächsten liegt. Trotz ausführlicher Tests mit über 100 Edge Cases, die alle fehlerfrei terminiert haben, liegt noch ein Fehler im Code. Bisher konnte ich jedoch keinen Fall finden, der nicht korrekt funktioniert.
Kann jemand von euch vielleicht einen Blick darauf werfen und mir helfen, mögliche Schwachstellen oder Fehler zu identifizieren? Ich wäre für jeden Tipp oder Testfall, der mein Problem offenlegen könnte, sehr dankbar!

  1.  Suche nach einem Wert 5 of 7 tests passing
  2. Die Methode 
  3. int search(int[] sortedData, int value, Result result)
  4.  soll mittels binärer Suche nach dem Index vom übergebenen Wert suchen.
  5. Dabei wird immer der mittlere Wert vom Suchbereich angesehen. Falls dies der gesuchte Wert ist, kann dessen Index zurück gegeben werden. Ansonsten verkleinert sich der Suchbereich auf die Indices, in denen der gesuchte Wert noch liegen kann. Falls der Suchbereich nur noch einen Wert enthält, soll ebenfalls abgebrochen werden.
  6. Wenn der Wert nicht im Array enthalten ist, soll stattdessen der Index vom nächst größeren oder nächst kleineren Wert zurückgegeben werden. Welcher der beiden Indices ist dabei egal, solange der zurückgegebene Index im Array liegt.
Code: 

public static int search(int[] sortedData, int value, Result result) {
     int left = 0;
    int right = sortedData.length - 1;
    int nearestindex = -1;
    int currentSmallest = Integer.MAX_VALUE;

    while(left <= right) {
        int middle = left + (right - left) / 2;
        int difference = Math.abs(value - sortedData[middle]);

        if(difference < currentSmallest) {
            currentSmallest = difference;
            nearestindex = middle;
        } else if(difference == currentSmallest) {
            if(Math.abs(value - nearestindex) > Math.abs(value - middle)) {
                nearestindex = middle;
            }
        }
        result.addStep(middle);

        if(sortedData[middle] == value) {
            return middle;
        }
        if (sortedData[middle] < value) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return nearestindex;
}
Bild zum Beitrag
Java, Programmiersprache, Algorithmus, binary
Kann mir jemand mit dem programmieren helfen?

Ich habe den Arduino-Doodlebot ( ein roboter der malen kann ) gebaut und versuche nun ihn so zu programmieren, dass er "HALLO" schreibt, jedoch schreibt er statt "HALLO" einfach ein H und dann noch eins undso weiter (er hört nicht auf ).

Hier ist der Code:

//

#include <Servo.h>

// setup servo

int servoPin = 8;

int PEN_DOWN = 90; // angle of servo when pen is down

int PEN_UP = 180;   // angle of servo when pen is up

Servo penServo;

float wheel_dia=82; //    # mm (increase = spiral out)

float wheel_base=112; //    # mm (increase = spiral in, ccw)

int steps_rev=128; //        # 512 for 64x gearbox, 128 for 16x gearbox

int delay_time=6; //         # time between steps in ms

// Stepper sequence org->pink->blue->yel

int L_stepper_pins[] = {12, 10, 9, 11};

int R_stepper_pins[] = {4, 6, 7, 5};

int fwd_mask[][4] =  {{1, 0, 1, 0},

                      {0, 1, 1, 0},

                      {0, 1, 0, 1},

                      {1, 0, 0, 1}};

int rev_mask[][4] =  {{1, 0, 0, 1},

                      {0, 1, 0, 1},

                      {0, 1, 1, 0},

                      {1, 0, 1, 0}};

void setup() {

  randomSeed(analogRead(1));

  Serial.begin(9600);

  for(int pin=0; pin<4; pin++){

    pinMode(L_stepper_pins[pin], OUTPUT);

    digitalWrite(L_stepper_pins[pin], LOW);

    pinMode(R_stepper_pins[pin], OUTPUT);

    digitalWrite(R_stepper_pins[pin], LOW);

  }

  penServo.attach(servoPin);

  Serial.println("setup");

 

  penup();

 

  delay(1000);

}

void loop(){ // draw a calibration box 4 times

  pendown();

  for(int x=0; x<12; x++){

    pendown();

    forward(80);

    backward(40);

    right(90);

    forward(30);

    left(90);

    forward(40);

    backward(80);

    penup();

    right(90);

    forward(10);

    left(90);

    pendown();

    forward(80);

    right(90);

    forward(30);

    right(90);

    forward(40);

    right(90);

    forward(30);

    backward(30);

    left(90);

    forward(40);

    left(90);

    penup();

    forward(10);

    left(90);

    pendown();

    forward(80);

    backward(80);

    right(90);

    forward(30);

    penup();

    forward(10);

    left(90);

    pendown();

    forward(80);

    backward(80);

    right(90);

    forward(30);

    penup();

    forward(10);

    left(90);

    pendown();

    forward(80);

    left(90);

    forward(30);

    left(90);

    forward(80);

    left(90);

    forward(30);

    penup();

    left(90);

    forward(100);

    penup();

  }

  penup();

  done();      // releases stepper motor

  while(1);    // wait for reset

}

// ----- HELPER FUNCTIONS -----------

int step(float distance){

  int steps = distance * steps_rev / (wheel_dia * 3.1412); //24.61

  /*

  Serial.print(distance);

  Serial.print(" ");

  Serial.print(steps_rev);

  Serial.print(" ");  

  Serial.print(wheel_dia);

  Serial.print(" ");  

  Serial.println(steps);

  delay(1000);*/

  return steps;  

}

void forward(float distance){

  int steps = step(distance);

  Serial.println(steps);

  for(int step=0; step<steps; step++){

    for(int mask=0; mask<4; mask++){

      for(int pin=0; pin<4; pin++){

        digitalWrite(L_stepper_pins[pin], rev_mask[mask][pin]);

        digitalWrite(R_stepper_pins[pin], fwd_mask[mask][pin]);

      }

      delay(delay_time);

    }

  }

}

void backward(float distance){

  int steps = step(distance);

  for(int step=0; step<steps; step++){

    for(int mask=0; mask<4; mask++){

      for(int pin=0; pin<4; pin++){

        digitalWrite(L_stepper_pins[pin], fwd_mask[mask][pin]);

        digitalWrite(R_stepper_pins[pin], rev_mask[mask][pin]);

      }

      delay(delay_time);

    }

  }

}

void right(float degrees){

  float rotation = degrees / 360.0;

  float distance = wheel_base * 3.1412 * rotation;

  int steps = step(distance);

  for(int step=0; step<steps; step++){

    for(int mask=0; mask<4; mask++){

      for(int pin=0; pin<4; pin++){

        digitalWrite(R_stepper_pins[pin], rev_mask[mask][pin]);

        digitalWrite(L_stepper_pins[pin], rev_mask[mask][pin]);

      }

      delay(delay_time);

    }

  }  

}

void left(float degrees){

  float rotation = degrees / 360.0;

  float distance = wheel_base * 3.1412 * rotation;

  int steps = step(distance);

  for(int step=0; step<steps; step++){

    for(int mask=0; mask<4; mask++){

      for(int pin=0; pin<4; pin++){

        digitalWrite(R_stepper_pins[pin], fwd_mask[mask][pin]);

        digitalWrite(L_stepper_pins[pin], fwd_mask[mask][pin]);

      }

      delay(delay_time);

    }

  }  

}

void done(){ // unlock stepper to save battery

  for(int mask=0; mask<4; mask++){

    for(int pin=0; pin<4; pin++){

      digitalWrite(R_stepper_pins[pin], LOW);

      digitalWrite(L_stepper_pins[pin], LOW);

    }

    delay(delay_time);

  }

}

void penup(){

  delay(250);

  Serial.println("PEN_UP()");

  penServo.write(PEN_UP);

  delay(250);

}

void pendown(){

  delay(250);  

  Serial.println("PEN_DOWN()");

  penServo.write(PEN_DOWN);

  delay(250);

}

Computer, Cplusplus, CPP, Programmiersprache, Algorithmus, C (Programmiersprache), Arduino Uno

Meistgelesene Beiträge zum Thema Algorithmus