Binary Search Help

  PFont font;
  int titleScreen = 0;
  int gameScreen = 1;
  int resultScreen = 2;
  int gameState;
  int countDownTimer;
  int countUpTimer;
  //Reminder: Add three zeroes to the end of desired time in Game Duration
  int gameDuration = 60000;
  String guess = "";
  int wordLimit = 20;
  int scoreCounter = 0;
  String[] wordArray;
  char[] alphabet = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', };
  char[] vowels = {'a', 'e', 'i', 'o', 'u', 'y', };
  char[] wheelOfFortune = {'r', 's', 't', 'l', 'n', 'e', };
  String scrambled = "";
  int maxRandomLetters = 7;
  int maxRandomVowels = 2;
  //WOF - Wheel Of Fortune
  int maxRandomWOF = 3;
  int results;
  boolean charInRandom;
  String feedback = "";
  String savedWords[] = new String [30]; 

  
  
  void setup() {
    background(#A73333);
    size(1280, 640);
    wordArray = loadStrings("word_dictionary.txt");
    font = createFont("SF Slapstick Comic Bold.ttf", 60);
    textFont(font);
  }
  void draw() {
    if (gameState == titleScreen) {
      titleScreen();
    } 
    else if (gameState == gameScreen) {
      gameScreen();
    } 
    else if (gameState == resultScreen) {
      resultScreen();
    }
  } 
  void keyPressed() {
  
    if (gameState == titleScreen && keyCode == ' ') {
      gameState = gameScreen;
      countUpTimer = millis();
      scrambled();
    }
    if (gameState == resultScreen && keyCode == ' ') {
      gameState = gameScreen;
      scoreCounter = 0;
      countUpTimer = millis();
      scrambled();
    }
    if (gameState == resultScreen && (key == 'm' || key == 'M')) {
      gameState = titleScreen;
      scoreCounter = 0;
    }
    if (gameState == gameScreen && key >= 'a' && key <= 'z' ||
      gameState == gameScreen && key >= 'A' && key <= 'Z') {
      if ( guess == "" ) feedback = "";
      guess = guess + key;
      guess = guess.toLowerCase();
    }
    if (keyCode == BACKSPACE && guess.length() > 0) {
      guess = guess.substring(0, guess.length() - 1);
    }
    if (keyCode == ENTER && guess.length() > 0) {  
      wordCheck();
      letterInScrambled();
      wordSaved();
      guess = "";
    }
    if (guess.length() > wordLimit) {
      guess = guess.substring(0, wordLimit);
    }
  }

  boolean letterInScrambled() {
  
    String letterFound = scrambled;
    for (int i = 0; i < guess.length(); i++) {
      boolean charInRandom = false;
      for (int j = 0; j < letterFound.length(); j++) {
        if (guess.charAt(i) == letterFound.charAt(j)) {
          charInRandom = true;
          letterFound = letterFound.substring(0, j) + letterFound.substring(j+1, letterFound.length());
          break;
        }
      }
      if (!charInRandom) {
        feedback = "Invalid Letter(s)";
        return false;
      }
    }
    return true;
  }

  // returns the valid word list that is found in 
  // data/word_dictionary.text
  String[] getWordArray()
  {
    String[] wordArray = loadStrings("word_dictionary.txt");
    sort(wordArray);
    return wordArray;
  }
  
  // returns an array of characters that are valid for the player
  // to type as parts of their anagram puzzle
  char[] getValidCharArray()
  {
    String[] tempCharArray = loadStrings("valid_keys.txt");
    char validCharArray[] = new char[tempCharArray.length];
    for (int i = 0; i < tempCharArray.length; i++)
    {
      validCharArray[i] = tempCharArray[i].charAt(0);
    }    
    return validCharArray;
  }
  
  void printWords()
  {
    print("Printing all the words");
    String[] wordArray = getWordArray();
    for (int i = 0; i < wordArray.length; i++)
    {
      println(wordArray[i]);
    }
  }
  
  void printValidChars()
  {
    print("Printing all the valid characters");
    char[] validCharArray = getValidCharArray();
    for (int i = 0; i < validCharArray.length; i++)
    {
      println(validCharArray[i]);
    }
  }
  
  //void setup()
  //{
  //  println("testing the code");
  //  printWords();
  //  printValidChars();
  //}

  void gameScreen() {
  
    background(#A73333);
    fill (#29C190);
  
    countDownTimer = 60 - (millis() - countUpTimer)/1000;
    if (countDownTimer <=0) {
      gameState = resultScreen;
      guess = "";
      scrambled = "";
      feedback = "";
    }
    
    text (countDownTimer, width/2, height/2);
    text (guess, width/2, height/4);
    text ("Score:" + scoreCounter, 100, 25);
    text (scrambled, width/2, +100);
    text (feedback, width/2, height-100);
  }

  void resultScreen() {
  
    background(#A73333);
  
    results = scoreCounter;
    text("Results: " + results, width/2, height/2);
    text("Press |SPACEBAR| to go again", width/2, height/4);
    text ("Press |M| to go back to the main menu", width/2, height/4*3);
  }

  void scrambled() {
    for (int i = 0; i < maxRandomLetters; i++) {
      scrambled += alphabet[(int) random(0, alphabet.length)];
    }
    for (int i = 0; i < maxRandomVowels; i++) {
      scrambled += vowels[(int) random(0, vowels.length)];
    }
    for (int i = 0; i < maxRandomWOF; i++) {
      scrambled += wheelOfFortune[(int) random(0, wheelOfFortune.length)];
    }
  }

  void titleScreen() {
  
    background(#A73333);
    strokeWeight(10);
    fill(#29C190);
    textSize(70);
    textAlign(CENTER, CENTER);
  
    text("WELCOME TO", width / 2, height / 4);
    text("ANAGRAMS", width / 2, height / 2 - 75 );
    textSize(50);
    textAlign(CENTER, CENTER);
    text("Press 'SPACEBAR' to Start", width / 2, height / 2 + 25);
  }

  boolean wordCheck() {
  
    if (letterInScrambled()) {
      for (int i = 0; i < wordArray.length; i++) {
        if (guess .equals (wordArray[i].toLowerCase())) {
          //scoreCounter++;
          feedback = "Great Job";
          return true;
        }
      }
    } 
    feedback = "Invalid Word";
    return false;
  }

  boolean wordSaved() {
    if (wordCheck()) {
      for (int i = 0; i < savedWords.length; i++) {
        if ((guess .equals (savedWords[i]))) {
          feedback = "Word already used";
          return false;
        }
      }
      scoreCounter++;
    }
    addToArray(guess);
    return true;
  }
  void addToArray(String guess) {
    for (int i = 0; i < savedWords.length; i++) {
      if (savedWords [i] == null) {
        savedWords [i] = guess;
        break;
      }
    }
  }

My teacher says that I need to implement a Binary Search function into my program. I do not know how to start this though. Can someone help me? I have pasted my code for reference. It is an anagrams game that uses linear search to find a matching word in a dictionary.

can you pls cut down your code to a part what
-a- runs ( without using files… )
-b- is the part you need help with

a binary search works on a sorted list and starts in the middle
but does not work on a list of words so easy,
as a ‘equals’ work, but a is > or < not
( what would tell you to search on in the upper or lower middle section )

but you can after the SORT
search for the index where the first matching character appears,
and start to match from there on…
that might give some SPEED UP, and that is what a binary search is about,
to be faster.

and that leads to the next “job”
you would need some timer code to proof
that your new search is faster.

a complete other way might be the use of
https://processing.org/reference/IntDict.html
you should compare it to your approach.

test
IntDict inventory;
String[] lines, words;
String find = "Lorem";
boolean gotit = false;
long startT,stopT,dT;

void setup() {
  size(200, 200);
  inventory = new IntDict();
  lines = loadStrings("http://websitetips.com/articles/copy/lorem/ipsum.txt");
  for ( String l : lines ) {
    words = split(l, ' ');
    for ( String word : words )  inventory.add(word, 1);
  }
  //println(inventory);
  println("we have "+inventory.size()+" entries");
  startT = millis();
  inventory.sortKeys();                              // sort alphabetically
  gotit = inventory.hasKey(find);                    // look for search string
  stopT = millis();
  dT = stopT - startT;
  if ( gotit ) {
    println("Yes, we found _" + find + "_: " + inventory.get(find) + " times");
  } else {
    println("Sorry, no _" + find + "_");
  }
  println(" and needed for sort and search " + dT + " msec" );
}


1 Like