Object-Oriented Programming with Java, part I + II

This material is licensed under the Creative Commons BY-NC-SA license, which means that you can use it and distribute it freely so long as you do not erase the names of the original authors. If you make changes in the material and want to distribute this altered version of the material, you have to license it with a similar free license. The use of the material for commercial use is prohibited without a separate agreement.

Authors: Arto Hellas, Matti Luukkainen
Translators to English: Emilia Hjelm, Alex H. Virtanen, Matti Luukkainen, Virpi Sumu, Birunthan Mohanathas, Etiënne Goossens
Extra material added by: Etiënne Goossens, Maurice Snoeren, Johan Talboom
Adapted for Informatica by: Ruud Hermans

The course is maintained by Technische Informatica Breda

Searching

In addition to sorting, another very typical problem that a programmer runs into is finding a certain value in an array. Earlier, we’ve implemented methods that search for values in lists and arrays. In the case of arrays, values and strings can be searched for in the following way:

public static boolean isInArray(int[] array, int searchingFor) {
    for ( int value : array ) {
       if ( value == searchingFor )  {
           return true;
       }
    }

    return false;
}

public static boolean isWordInArray(String[] array, String searchingFor) {
    for ( String word: array ) {
        if ( word.equals(searchingFor) )  {
            return true;
        }
    }

    return false;
}

An implementation like this is the best we’ve been able to do so far. The downside of the method is that, if the array has a very large amount of values in it, the search will take a lot of time. In the worst case scenario the method goes through every single cell in the array. This means that going through an array that has 16777216 cells does 16777216 cell inspections.

On the other hand, if the values in an array are ordered by size, the search can be done in a notably faster way by applying a technique called binary search. Let’s investigate the idea of binary search with this array:

// indexes   0   1   2   3    4   5    6   7   8   9  10
// values   -7  -3   3   7   11  15   17  21  24  28  30

Let’s assume that we want to find the value 17. Let’s utilize the information that the values of the array are in order instead of going through the array from the beginning. Let’s inspect the middle cell of the array. The middle cell is 5 (the largest index 10 divided by two). The middle cell is marked with the asterisk:

                                  *
// indexes   0   1   2   3    4   5    6   7   8   9  10
// values   -7  -3   3   7   11  15   17  21  24  28  30

At the middle is the value 15, which was not the value we were looking for. We’re looking for the value 17, so since the cells of the array are ordered by size, the value cannot be on the left side of the 15. So we can determine that all indexes that are smaller or equal to 5 do not have the value we are looking for.

The area where we are searching for the value we want to find can now be limited to values that are on the right side of the index 5, or in other words, in the indexes [6, 10] (6, 7, 8, 9, 10). In the following, the searched value cannot be in the part of the array which is red:

// indexes    ~~0   1   2   3   4    5~~    6    7   8   9  10
// values    ~~-7  -3   3   7  11   15~~   17   21  24  28  30

Next, let’s inspect the middle index of the area that we have left; the middle index of indexes 6-10. The middle index can be found by getting the sum of the smallest and largest index and dividing it by two: (6+10)/2 = 16/2 = 8. The index 8 is marked with the asterisk below.

                                                *
// indexes    ~~0   1   2   3   4    5~~    6   7   8   9   10
// values    ~~-7  -3   3   7  11   15~~   17   21  24  28  30

In index 8, we have the value 24, which was not the value we were looking for. Because the values in the array are ordered by size, the value we are searching for can not, in any case, be on the right side of the value 24. We can deduce that all indexes that are larger or equal to 8 can not contain the value we are looking for. The search area gets narrowed down again, the grey areas have been dealt with:

// indexes    ~~0   1   2   3   4    5~~    6   7   ~~8   9   10~~
// values    ~~-7  -3   3   7  11   15~~   17   21  ~~24  28  30~~

The search continues. Let’s inspect the middle index of the area that we have left to search, that is, the middle index of indexes 6-7. The middle index can again be found out by getting the sum of the smallest and largest index of the search area and then dividing it by two: (6+7)/2 = 6.5, which is rounded down to 6. The spot has been marked with the asterisk.

                                          *
// indexes    ~~0   1   2   3   4    5~~    6    7   ~~8   9  10~~
// values    ~~-7  -3   3   7  11   15~~   17   21  ~~24  28  30~~

In the index 6 we have the value 17, which is the same as the value we’ve been looking for. We can stop the search and report that the value we searched for is in the array. If the value wouldn’t have been in the array - for example if the searched-for value would’ve been 16 - the search area would have eventually been reduced to nothing.

                                          *
// indexes    ~~0   1   2   3   4    5~~    6   7   ~~8   9   10~~
// values    ~~-7  -3   3   7  11    15~~   17  21  ~~24  28  30~~

So for the idea of binary search to become clear to you, simulate with pen and paper how the binary search works when the array is the one below and first you’re searching for value 33 and then value 1.

// indexes   0   1   2   3   4   5   6   7   8   9  10  11  12  13
// values   -5  -2   3   5   8  11  14  20  22  26  29  33  38  41

With the help of binary search we look for cells by always halving the inspected area. This enables us to search in a very efficient way. For example, an array of size 16 can be divided in half up to 4 times, so 16 -> 8 -> 4 -> 2 -> 1. On the other hand, an array that has 16777216 cells can be halved up to 24 times. This means that with binary search we only need to inspect up to 24 cells in an array that has 16777216 cells in order to find our desired cell.

The efficiency of binary search can be inspected with logarithms. A base two logarithm ($log_2$) of the number 16777216 is 24 – with the base two logarithm we can calculate how many times a number can be halved. Respectively the base two logarithm of the number 4294967296 ($log_2 4294967296$) is 32. This means that searching from a sorted array of 4294967296 different values would only take up to 32 cell inspections. Efficiency is an essential part of computer science.

Exercise searching-1: Guessing game

In this assignment we’ll make an AI, which guesses the number the player is thinking about. The AI assumes that the number is between lowerLimit…upperLimit. The start of the game provides these limits to the method as parameters that makes the game happen. The AI asks the player questions in the format “Is your number greater than X?” and deduce the correct answer from the answers the player gives.

The AI keeps track of the search area with the help of the variables lowerLimit and upperLimit. The AI always asks if the player’s number is greater than the average of these two numbers, and based on the answers the search area gets halved each time. In the end the lowerLimit and upperLimit are the same and the number the user is thinking of has been revealed.

In the following example the user chooses the number 44:

Think of a number between 1...100.
I promise you that I can guess the number you are thinking of with 7 questions.

Next I'll present you a series of questions. Answer them honestly.

Is your number greater than 50? (y/n)
~~n~~
Is your number greater than 25? (y/n)
~~y~~
Is your number greater than 38? (y/n)
~~y~~
Is your number greater than 44? (y/n)
~~n~~
Is your number greater than 41? (y/n)
~~y~~
Is your number greater than 43? (y/n)
~~y~~
The number you're thinking of is 44.

In the above example the possible value range is first 1…100. When the user tells the program that the number is not greater than 50 the possible range is 1…50. When the user says that the number is greater than 25, the range is 26…50. The deduction proceeds in the same fashion until the number 44 is reached.

In accordance to the principles of halving, or binary search, the possible search area is halved after each question in which case the number of required questions is small. Even between the numbers 1…100000 it shouldn’t take more than 20 questions.

The program skeleton of the class GuessingGame that implements this is the following:

public class GuessingGame {

    private Scanner reader;

    public GuessingGame() {
        this.reader = new Scanner(System.in);
    }

    public void play(int lowerLimit, int upperLimit) {
        instructions(upperLimit, lowerlimit);

        // write the game logic here
    }

    // implement here the methods isGreaterThan and average

    public void instructions(int lowerLimit, int upperLimit) {
        int maxQuestions = howManyTimesHalvable(upperLimit - lowerLimit);

        System.out.println("Think of a number between " + lowerLimit + "..." + upperLimit + ".");

        System.out.println("I promise you that I can guess the number you are thinking of with " + maxQuestions + " questions.");
        System.out.println("");
        System.out.println("Next I'll present you with a series of questions. Answer them honestly.");
        System.out.println("");
    }

    // a helper method:
    public static int howManyTimesHalvable(int number) {
        // we create a base two logarithm  of the given value
        // Below we swap the base number to base two logarithms!
        return (int) (Math.log(number) / Math.log(2)) + 1;
    }
}

The game is started the in following manner:

GuessingGame game = new GuessingGame();

// we play two rounds
game.play(1,10);  // value to be guessed now within range 1-10
game.play(10,99);  // value to be guessed now within range 10-99

We’ll implement this assignment in steps.

Exercise searching-1.1: Is greater than

Implement the method public boolean isGreaterThan(int value), which presents the user with a question:

"Is your number greater than given value? (y/n)"

The method returns the value true if the user replies “y”, otherwise false.

Test your method

GuessingGame game = new GuessingGame();

System.out.println(game.isGreaterThan(32));

Is your number greater than 32? (y/n)
y
true

Exercise searching-1.2: Average

Implement the method public int average(int firstNumber, int secondNumber), which calculates the average of the given values. Notice that Java rounds floating numbers down automatically, in our case this is perfectly fine.

GuessingGame game = new GuessingGame();
System.out.println(game.average(3, 4));

3

GuessingGame game = new GuessingGame();
System.out.println(game.average(6, 12));

9

Exercise searching-1.3: Guessing logic

Write the actual guessing logic in the method play of the class GuessingGame. You’ll need at least one loop and a query in which you ask the user if their number is greater than the average of the lowerLimit and upperLimit. Change the upperLimit or lowerLimit depending on the user’s reply.

Keep doing the loop until lowerLimit and upperLimit are the same! You can also test the game with smaller lower- and upperLimit values:

Think of a number between 1...4.
I promise you that I can guess the number you are thinking of with 2 questions.

Next I'll present you with a series of questions. Answer them honestly.

Is your number greater than 2? (y/n)
~~y~~
Is your number greater than 3? (y/n)
~~y~~
The number you're thinking of is 4.

Exercise searching-2: Implementation of binary search

The template you get from the test automaton has a start for an implementation of binary search. The class BinarySearch holds a method public static boolean search(int[] array, int searchedValue), the job of which is to figure out, by using binary search, if the value given as a parameter is in the sorted array that is also given as parameter.

The method search does not work yet, however. Finish the method’s implementation into a real binary search.

For testing, a separate main program can be found in the class Main, which has a frame like this:

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // Here you can test binary search
        int[] array = { -3, 2, 3, 4, 7, 8, 12 };
        Scanner reader = new Scanner(System.in);

        System.out.print("Values of the array: " + Arrays.toString(array));
        System.out.println();

        System.out.print("Enter searched number: ");
        String searchedValue = reader.nextLine();
        System.out.println();

        boolean result = BinarySearch.search(array, Integer.parseInt(searchedValue));

        // Print the binary search result here
    }
}

The execution of the program looks like this:

Values of the array: [-3, 2, 3, 4, 7, 8, 12]

Enter searcher number: ~~8~~

Value 8 is in the array

Values of the array: [-3, 2, 3, 4, 7, 8, 12]

Enter searcher number: ~~99~~

Value 99 is not in the array