Gyakorlati alapok
Keresések választási lehetőséggel
A fejezet gondolati és tartalmi előzményei Keresések rendezett tömbben című fejezetben tanulmányozhatók.
Ebben a fejezetben a jelen fejezetcsomag kívánalmai szerint mindent külön metódusokba csoportosítunk, legfőképpen a publikált felezéses és bináris keresést, továbbá:
-
véletlenszám-generálás egy tömbbe - static int[]veletlenSzamGenerator()
-
keresett szám bekérése (csak a számtartomány ellenőrzése) - static int szamBekeres()
-
egyszerű cserés tömbelem-rendezés - static int[]cseresRendezes(int[] tomb)
-
felezéses keresés - static int[] felezesesKereses(int[] tomb, int keresettSzam)
-
bináris keresés - static int[] binarisKereses(int[] tomb, int keresettSzam)
-
kiértékelés és eredménykiírás - static void kiertekeles(int[] talalatiTomb)
További sajátos feltétel: a felhasználó választhasson aközött, hogy melyik kereső algoritmust futtatja le, a felezéses vagy a bináris keresést (String[] menu = new String[] {"1 - Felezéses keresés", "2 - Bináris keresés", "0 - Kilépés"};). Futási különbségeket persze nem fog érzékelni, azok csak nagy léptékek, például egy óriási méretű adatbázis esetén jönnek elő. Valójában a menüből adódóan képes egymás után mindkét algoritmust lefuttatni ugyanarra a bemeneti adathalmazra, amivel nyilvánvalóan tesztelheti is pontosságukat.
Az előzmények során (Keresések rendezett tömbben című fejezet) az algoritmusok eredménykiíráskor nem vették figyelembe a számredundanciát, azaz több azonos szám esetén az utolsó indexet írták ki. Például:
7
A rendezett tömb:
7 7 22 31 36 50 62 77 89 93
A keresett benne van a tömbben, a(z) 2. indexen.
A probléma természetesen orvosolható egy olyan véletlenszám-generátorral, amelyik ezt nem engedi meg, azaz csakis egyedi véletlenszámokat állít elő (static int[]veletlenSzamGenerator()).
Nézzük meg a futtatható Java-kódot:
import java.util.*;
public class Main {
static int[]veletlenSzamGenerator(){
Random rnd = new Random();
int[] tombVeletlenSzam = new int[10];
int szamlalo = 0;
while(szamlalo < 10) {
int szam = rnd.nextInt(100) + 1;
boolean benneVan = false;
for(int j = 0; j < szamlalo; j++) {
if(tombVeletlenSzam[j] == szam) {
benneVan =
true;
}
}
if(benneVan == false) {
tombVeletlenSzam[szamlalo] = szam;
szamlalo++;
}
}
return tombVeletlenSzam;
}
static int[]cseresRendezes(int[] tomb){
for(int i = 0; i <= tomb.length - 1; i++){
for(int j = i + 1; j <= tomb.length -
1; j++){
if(tomb[i] >
tomb[j]){
int tarolo = tomb[i];
tomb[i] = tomb[j];
tomb[j] = tarolo;
}
}
}
return tomb;
}
static void tombKiiras(int[] tomb){
for(int i = 0; i < tomb.length; i++){
System.out.print(tomb[i] + " ");
}
}
static int szamBekeres(){
Scanner in = new Scanner (System.in);
String bemenetiAdat = new String();
System.out.println ("\nKérem, hogy adja meg a számot!");
bemenetiAdat = in.nextLine();
int keresettSzam = Integer.parseInt(bemenetiAdat);
while (keresettSzam < 1 || keresettSzam > 100){
System.out.println("Kérem, hogy csak
pozitív egész számot adjon meg 1 és 100 között!");
bemenetiAdat = in.nextLine();
keresettSzam =
Integer.parseInt(bemenetiAdat);
}
return keresettSzam;
}
static int[] binarisKereses(int[] tomb, int keresettSzam) {
int[] talalatiTomb = new int[2];
int alsoHatar = 0;
int felsoHatar = tomb.length;
boolean talalat = false;
int kozep = -1;
while (!talalat && alsoHatar <= felsoHatar) {
kozep = (alsoHatar + felsoHatar) / 2;
if(keresettSzam == tomb[kozep]) {
talalat =
true;
talalatiTomb[0] = 1;
talalatiTomb[1] = kozep+1;
} else if(tomb[kozep] < keresettSzam)
{
alsoHatar = kozep+1;
} else {
felsoHatar = kozep-1;
}
}
return talalatiTomb;
}
static int[] felezesesKereses(int[] tomb, int keresettSzam){
int[] talalatiTomb = new int[2];
boolean talalat = false;
int kozep = tomb.length / 2;
if((keresettSzam >= tomb[kozep])){
for(int i = kozep; i < tomb.length;
i++){
if(tomb[i] ==
keresettSzam){
talalat = true;
talalatiTomb[0] = 1;
talalatiTomb[1] = i + 1;
break;
}
}
}
else if(keresettSzam < tomb[kozep]){
for(int i = kozep; i >= 0; i--){
if((tomb[i]
== keresettSzam)){
talalat = true;
talalatiTomb[0] = 1;
talalatiTomb[1] = i + 1;
break;
}
}
}
return talalatiTomb;
}
static void kiertekeles(int[] talalatiTomb){
if(talalatiTomb[0] == 1) {
System.out.println("A szám benne van
a tömbben a(z) " + talalatiTomb[1] + ". indexen");
}
else{
System.out.println("A szám nincs
benne a tömbben.");
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] tombVeletlenSzam = new int[10];
int[] tombVeletlenSzamRendezett = new int[10];
int[] talalatiTomb = new int[2];
int keresettSzam = 0;
boolean voltMuvelet = false;
String[] menu = new String[] {"1 - Felezéses keresés", "2 -
Bináris keresés", "0 - Kilépés"};
tombVeletlenSzam = veletlenSzamGenerator();
System.out.println("A véletlenszámok:");
tombKiiras(tombVeletlenSzam);
System.out.println();
tombVeletlenSzamRendezett = cseresRendezes(tombVeletlenSzam);
System.out.println("\nA véletlenszámok rendezve:");
tombKiiras(tombVeletlenSzamRendezett);
System.out.println();
keresettSzam = szamBekeres();
while(true) {
System.out.println("\nKérem válasszon
az alábbi lehetőségekből: ");
for(int i = 0; i < menu.length; i++)
{
System.out.println(menu[i]);
}
String valasztas = in.nextLine();
if("1".equals(valasztas)) {
talalatiTomb =
felezesesKereses(tombVeletlenSzamRendezett, keresettSzam);
kiertekeles(talalatiTomb);
voltMuvelet = true;
}
if("2".equals(valasztas)) {
talalatiTomb =
binarisKereses(tombVeletlenSzamRendezett, keresettSzam);
kiertekeles(talalatiTomb);
voltMuvelet = true;
}
if("0".equals(valasztas)) {
System.out.println("\nViszlát!");
System.exit(0);
}
}
}
}
Végeredmény (például):
A véletlenszámok:
12 62 83 70 46 66 97 10 2 23
A véletlenszámok rendezve:
2 10 12 23 46 62 66 70 83 97
Kérem, hogy adja meg a számot!
0
Kérem, hogy csak pozitív egész számot adjon meg 1 és 100 között!
102
Kérem, hogy csak pozitív egész számot adjon meg 1 és 100 között!
70
Kérem válasszon az alábbi lehetőségekből:
1 - Felezéses keresés
2 - Bináris keresés
0 - Kilépés
1
A szám benne van a tömbben a(z) 8. indexen
Kérem válasszon az alábbi lehetőségekből:
1 - Felezéses keresés
2 - Bináris keresés
0 - Kilépés
2
A szám benne van a tömbben a(z) 8. indexen
Kérem válasszon az alábbi lehetőségekből:
1 - Felezéses keresés
2 - Bináris keresés
0 - Kilépés
0
Viszlát!
Pénzes László