Gyakorlati alapok
Keresések rendezett tömbben
Ebben a fejezetben 2 db, rendezett tömbök esetén jól felhasználható keresési megoldást fogunk tanulmányozni. Mindegyiknek van egy hasznos, irányadó alapötlete, amelyik aztán gondolati vezérfonalként implementálásra kerül.
Kezdjük a felezéses algoritmussal. Alapötlete, hogy elfelezzük az, ebben az esetben 10 db véletlenszámmal feltöltött, de rendezett elemű tömb méretét és kiválasztjuk 1. felét a keresés végrehajtására. Optimális esetben a keresett szám ott van, ekkor keresési időnk a tervezetthez képest szintígy elfeleződött. Ha nincs ott, akkor már csak a 2. felében lehet vagy nincs benne a tömbben. Az alábbi algoritmus felépítése:
-
komponensek deklarációi és inicializálásuk
-
tömb rendezés előtt
-
keresett szám bekérése (csak a számtartomány ellenőrzése)
-
egyszerű cserés tömbelem-rendezés
-
tömb rendezés után
-
felezéses keresés
-
kiértékelés és eredménykiírás
Az algoritmus eredménykiíráskor nem veszi figyelembe a számredundanciát, azaz több azonos szám esetén az utolsó indexet írja 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.
Nézzük meg a felezéses algoritmus futtatható Java-kódját:
import java.util.*;
public class Main {
public static void main(String[] args) {
int [] tomb = new int[10];
int keresettSzam = 0;
int keresettSzamIndex = 0;
Random rnd = new Random();
Scanner in = new Scanner(System.in);
boolean talalat = false;
System.out.println("Tömb rendezés előtt:");
for(int i = 0; i < tomb.length; i++){
tomb[i] = rnd.nextInt(100) + 1;
System.out.print(tomb[i] + " ");
}
System.out.println();
do{
System.out.print("Kérem, hogy adjon meg egy számot (0 és 100 között):\n");
String szamString = in.nextLine();
keresettSzam = Integer.parseInt(szamString);
}while (keresettSzam < 1 || keresettSzam > 99);
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;
}
}
}
System.out.println("A rendezett tömb:");
for(int i = 0; i < tomb.length; i++) {
System.out.print(tomb[i] + " ");
}
System.out.println();
int kozep = tomb.length / 2;
if((keresettSzam >= tomb[kozep])){
for(int i = kozep; i < tomb.length; i++){
if(tomb[i] == keresettSzam){
talalat = true;
keresettSzamIndex = i;
break;
}
}
}
else if(keresettSzam < tomb[kozep]){
for(int i = kozep; i >= 0; i--){
if((tomb[i] == keresettSzam)){
talalat = true;
keresettSzamIndex = i;
break;
}
}
}
if(talalat == true){
System.out.println("\nA keresett benne van a tömbben,
a(z) " +
(keresettSzamIndex+1) + ". indexen.");
}
else
System.out.println("\nA keresett szám nincs a tömbben.");
}
}
Végeredmény (például):
Tömb rendezés előtt:
8 22 35 27 61 27 86 84 53 52
Kérem, hogy adjon meg egy számot (1 és 100 között):
53
A rendezett tömb:
8 22 27 27 35 52 53 61 84 86
A keresett benne van a tömbben, a(z) 7. indexen.
A logaritmikus, másnéven bináris keresés (binary search) alapötlete a felezéses keresésből indul ki, ám azon túllép. Nemcsak hogy elfelezi a tömbméretet, hanem sikertelen keresés esetén tovább felezi azt (és így tovább). Tehát a keresés során minden egyes iterációban felezni lehet a következő iterációban résztvevő elemek számát, így egy n elemű tömbben log n lépésben megtalálható a keresett elem, vagy megállapítható hiánya. Mivel az összes többi feltétel teljesen azonos a fenti, felezéses algoritmussal, ezért a szöveget kis változtatásokkal idemásolom:
A logaritmikus algoritmus felépítése:
-
komponensek deklarációi és inicializálásuk
-
tömb rendezés előtt
-
keresett szám bekérése (csak a számtartomány ellenőrzése)
-
egyszerű cserés tömbelem-rendezés
-
tömb rendezés után
-
logaritmikus keresés
-
kiértékelés és eredménykiírás
Az algoritmus eredménykiíráskor nem veszi figyelembe a számredundanciát, azaz több azonos szám esetén az utolsó indexet írja 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.
Nézzük meg a bináris algoritmus futtatható Java-kódját:
import java.util.*;
public class Main {
public static void main(String[] args) {
int [] tomb = new int[10];
int keresettSzam = 0;
int keresettSzamIndex = 0;
Random rnd = new Random();
Scanner in = new Scanner(System.in);
boolean talalat = false;
System.out.println("Tömb rendezés előtt:");
for(int i = 0; i < tomb.length; i++){
tomb[i] = rnd.nextInt(100) + 1;
System.out.print(tomb[i] + " ");
}
System.out.println();
do{
System.out.print("Kérem, hogy adjon meg egy számot (0 és 100 között):\n");
String szamString = in.nextLine();
keresettSzam = Integer.parseInt(szamString);
}while (keresettSzam < 1 || keresettSzam > 99);
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;
}
}
}
System.out.println("A rendezett tömb:");
for(int i = 0; i < tomb.length; i++) {
System.out.print(tomb[i] + " ");
}
System.out.println();
int alsoHatar = 0;
int felsoHatar = tomb.length;
int kozep = -1;
while (!talalat && alsoHatar <= felsoHatar) {
kozep = (alsoHatar + felsoHatar) / 2;
if(keresettSzam == tomb[kozep]) {
talalat = true;
keresettSzamIndex = kozep;
}else if(tomb[kozep] < keresettSzam) {
alsoHatar = kozep+1;
}else {
felsoHatar = kozep-1;
}
}
if(talalat == true){
System.out.println("\nA keresett benne van a tömbben,
a(z) " +
(keresettSzamIndex+1) + ". indexen.");
}
else
System.out.println("\nA keresett szám nincs a tömbben.");
}
}
Végeredmény (például):
Tömb rendezés előtt:
7 100 67 67 10 51 58 45 28 54
Kérem, hogy adjon meg egy számot (1 és 100 között):
6
A rendezett tömb:
7 10 28 45 51 54 58 67 67 100
A keresett szám nincs a tömbben.
Pénzes László