I wrote the algorithm of the Basic Information Technology Engineer Examination as a practice in my own way.
A class created so that it can be used for practice such as linear search.
MessagePrinter.java
/**
*A class that prints a message of search results
*
* @author hatena
*
*/
import java.util.List;
public class MessagePrinter {
public void printFoundMessages(int targetNumber, List<Integer> targetList) {
System.out.println("Number of objects to search in the list" + targetNumber + "Existed.");
System.out.println("The search target list is" + targetList + "was.");
System.out.println("The index of the number of search targets is" + targetList.indexOf(targetNumber) + "is.");
}
public void printNotFoundMessages(int targetNumber, List<Integer> targetList) {
System.out.println("Number of objects to search in the list" + targetNumber + "Did not exist.");
System.out.println("The list to be searched is" + targetList + "was.");
}
}
The java.util.Random class had an ints () method that returned a specified range of IntStream.
I feel that the random numbers are biased. .. ..
RandomListCreator.java
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import lombok.AllArgsConstructor;
/**
*A class that creates a list of random positive integers.
*
* @author hatena
*
*/
@AllArgsConstructor
public class RandomListCreator {
public int lengthOfList;
public int maximumNumber;//ex:If you specify 50, the list generated will include 50.
/**
*A method that returns an unsorted list of integers of a specified length.
*
*
*/
public List<Integer> createRandUnorderdList() {
//Random number generation class
Random rand = new Random();
//@formatter:off
List<Integer> unorderdRandlist =
rand
.ints(this.lengthOfList, 0, this.maximumNumber + 1)
.boxed()
.collect(Collectors.toList());
//@formatter:on
return unorderdRandlist;
}
}
At the moment, only ascending order is supported.
BinSearch.java
import java.util.List;
import lombok.Data;
/**
*Binary search method (target sequences are currently only available in ascending order)
*
* @author hatena
*/
@Data
public class BinSearch {
//Start / center / end index
//Search target list, flag of whether found
private int beginIndex;
private int midIndex;
private int lastIndex;
private List<Integer> targetList;
private boolean isFound;
//constructor. Calculate the central index with the start and end indexes.
public BinSearch(List<Integer> targetList) {
this.targetList = targetList;
this.beginIndex = 0;
this.lastIndex = targetList.size() - 1;
this.midIndex = (this.beginIndex + this.lastIndex) / 2;
this.isFound = false;
}
/**
*Binary search method A method that performs the main body
*
*/
public void findTargetNumber(int targetNumber) {
//Continue searching while the leading index of the list to be checked is less than or equal to the closing index
//If not found, isFound remains false and the loop ends
while (beginIndex <= lastIndex) {
//Determine if the median of the list is equal to the number of targets
//If they are equal, update isFound and end the loop.
if (targetList.get(midIndex) == targetNumber) {
isFound = true;
break;
} else if (targetList.get(midIndex) > targetNumber) {
//Determine if the central index value of the list is larger, update the index to be checked
lastIndex = midIndex - 1;
midIndex = (beginIndex + lastIndex) / 2;
continue;
} else {
//Determine if the list center index value is smaller and update the index to be checked
beginIndex = midIndex + 1;
midIndex = (beginIndex + lastIndex) / 2;
continue;
}
}
}
}
MainBinSearch.java
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import bisearch.BinSearch;
import common.MessagePrinter;
import common.RandomListCreator;
/**
*Binary search method execution class
*
* @author hatena
*
*/
public class MainBinSearch {
public static void main(String[] args) {
//Create an instance for standard input and result display
Scanner scanner = new Scanner(System.in);
//Ask the user to enter the information (length, maximum number in the list) needed to create a random list.
//Instantiate a class that creates a random list
System.out.print("Enter the length of the list as a positive integer:");
int lengthOfList = scanner.nextInt();
System.out.print("Enter the maximum number to include in the list:");
int maximumNumber = scanner.nextInt();
//Create an ascending list of random numbers
RandomListCreator listCreator = new RandomListCreator(lengthOfList, maximumNumber);
List<Integer> targetList = listCreator.createRandUnorderdList();
Collections.sort(targetList);
System.out.println("I made a list of random numbers in ascending order.");
//Enter the number you want to find as standard
System.out.print("Enter the number you want to search for 2 minutes:");
int targetNumber = scanner.nextInt();
//Instance creation for binary search, search method execution
BinSearch binSearch = new BinSearch(targetList);
binSearch.findTargetNumber(targetNumber);
//Create an instance for displaying messages
MessagePrinter messagePrinter = new MessagePrinter();
//Display a message according to the search result
if (binSearch.isFound()) {
messagePrinter.printFoundMessages(targetNumber, binSearch.getTargetList());
} else {
messagePrinter.printNotFoundMessages(targetNumber, binSearch.getTargetList());
}
scanner.close();
}
}
getIsFound is isFound and setIsFound is setFound (Reference).■ When the target number exists in the list
Enter the length of the list as a positive integer: 10
Enter the maximum number to include in the list: 15
I made a list of random numbers in ascending order.
Enter the number you want to search for 2 minutes:3
There were 3 search targets in the list.
The search target list is[0, 1, 2, 3, 6, 7, 8, 12, 13, 15]was.
The index of the number of objects to be searched is 3.
■ When the target number does not exist in the list
Enter the length of the list as a positive integer: 10
Enter the maximum number to include in the list: 15
I made a list of random numbers in ascending order.
Enter the number you want to search for 2 minutes:3
The number 3 to be searched was not found in the list.
The list to be searched is[1, 1, 8, 10, 10, 11, 11, 14, 14, 14]was.
Recommended Posts