** DRAFT ** NOT READY YET **

Binary Search

How did we end up talking about binary search? We started with a simple question: what are the chances that a few random letters put together can form an actual word? Here’s a simple strategy to answer this question.

form a random word
look up that word in a dictionary

The first part of the strategy is straight forward. It requires a method that returns a string with a given number of letters, chosen at random. In the code below ASCII_a and ALPHABET are integer constants with values 97 and 26 respectively. Constant ASCII_a points to the lower case char 'a'. And ALPHABET is the number of letters in the English alphabet.

static String randomWord(int howManyLetters) {
    // Initialize string to return
    String word = "";
    // Setup random number generator
    Random rng = new Random();
    // Repeat for as many letters as required
    for (int letter = 0; letter < howManyLetters; letter++) {
        // select a letter a-z at random
        char randomCharacter =  (char) (ASCII_a + rng.nextInt(ALPHABET));
        // add it to string
        word += randomCharacter;
    }
    return word;
}

The challenge now is to check if randomly formed strings like "ajopw", "uyvgq", "hello" etc, are actual words.

Let’s assume that we have a file with all the English words. We can tell if a given string is an actual word, based on the following pseudocode.

while not at end-of-file:
  if wordReadFromFile == givenRandomString
    return true
return false

The pseudocode above, can be implemented in Java, line-for-line:

while (file.hasNextLine())
  if (file.nextLine().equals(givenRandomString))
    return true;
return false;

The code snippet above assumes that file is a properly declared and initialized Scanner object. This object connects to a file with all english words, accessible from the computer’s filesystem.

Sometimes, often actually, the data we need are available online and they are not immediately accessible through our computer’s filesystem. In this case we have two choices: copy the file to our computer (if we have permission to do so and also space to store it) or access its contents over a computer network (again, if we have permission to do so). The Internet is a readily available network for most of us. And Java, like most programming languages, has a mechanism to access remote files that are available on the Web.

Let’s consider a file at the following location:

https://raw.githubusercontent.com/lgreco/IntroProgramming/main/data/words.txt

If we don’t want a copy of the file on our computer, we can write a program to scan it remotely. All we need is to tell Scanner where to find the file on the web:

URL url = new URL("https://raw.githubusercontent.com/lgreco/IntroProgramming/main/data/words.txt");
Scanner file = new Scanner(new InputStreamReader(url.openStream()));

The code snippet aove creates a Scanner object that connects to an InputStreamReader. This reader is a conduit, over the internet, between our computer and the website with the file we wish to process. That website is identified by a URL object.

Working with files is fun, but …

Files are, usually, slow to access. Specifically, they are slower compared to computer memory. Ideally, we want to read them once (maaaaybe twice) and bring their data into the computer memory (if there is room). The easiest (and often best) memory container we have at our disposal is, of course, the humble array.

How can we bring data from a file into an array? First, by making our life easier: let’s assume that each line in the file contains a single piece of data. Which is the case for the file with the english words.

How can we bring the data from the file into an array? Here, we hit a snag. Before adding data to an array, we must declare and initialize it. For that, we need to know how many elements the array will store. And so it is necessary to know how much data are stored in the file that we want to move to the array. The surrest way is to go through the file, count the data, use that number of initialize the array, and then move the data from the file to the array, i.e.:

N <--- count of data in the file
ourArray[] <--- new array[N]
for i = 0 to N
  ourArray[i] <--- data from file
  move to next line in the file

The pseudocode above suggests that we scan the file twice. First to count its data and then to move that data, one line at a time, to the array. The alternative is to anticipate the number of data we want to store, add a safety margin, and hope that we are correct. For example, we can guess that we need room for 50,000 elements in the array, double it to 100,000 to be safe, and try it. Worst case scenario, we’ll run into an out of bounds exception. Personally, I’d rather scan the file twice: once to count the data and make a precise declaration for the array, and once more to move the data from the file to the array.

The method to count the number of lines in a file is based on the following code:

// assume file is a properly assigned scanner object
int counter = 0;
while (file.hasNextLine()) {
  String s = file.nextLine();
  counter++;
}
return counter;

And the method to bring the data to an array is based on the following code

// assume N is the number of lines in the file, obtained by previous method
String data[] = new String[N];
// assume file is a properly assigned scanner object
for (int i=0; i < N; i++)
  data[i] = file.nextLine();
return data;

Working with sorted data