Wyszukiwanie Binarne

Jak w posortowanym zbiorze znaleźć konkretną wartość? Najprościej przeliterować się po każdym elemencie. Czyli jeśli wybierzesz liczbę z przedziału 1-100 i za każdym razem informacją zwrotną będzie czy dana liczba jest większa czy mniejsza od podanej przeze mnie, to w najgorszym wypadku będę potrzebował aż 100 prób żeby odkryć o jaką liczbę Ci chodzi.

A jak to zrobić szybciej? Tutaj przychodzi z pomocą algorytm wyszukiwania binarnego, tzn zgadujemy zawsze wartością równą połowy danego zbioru, czyli:

  1. Mając zakres wartości od 1 do 100, zaczynam od środka czyli 50.
  2. Otrzymując od Ciebie informację czy Twoja liczba jest mniejsza czy większa eliminuje 50 rekordów.
  3. Zakładając, że wybrana liczba to 33, moją następną odpowiedzią będzie 25, a następny zbiór będzie się zawierał w przedziale 25 -50 itd.
  4. Czyli maksymalna liczba prób przy zbiorze 100-elementowym wyniesie 7.

Dla porównania przy zbiorze 1 000 000 000 wyszukiwanie proste potrzebuje maksymalnie 1 000 000 000 a wyszukiwanie binarne tylko 32 próby.

Implementacja wyszukiwania binarnego wygląda następująco:

public int binarySearch (TreeSet<Integer> listOfNumber, int searchNumber)
{
int min = listOfNumber.first();
int max = listOfNumber.last();
int quess;

while (min <= max)
{
quess = (( min + max ) / 2) + 1;

if (quess == searchNumber)
{
return quess;
}
if (quess < searchNumber)
{
min = quess;
}
if (quess > searchNumber)
{
max = searchNumber;
}
}

return Integer.parseInt(null);
}

Używam TreeSeta gdyż z automatu jest posortowany. Nie ładnie ale rzucam nullem gdy wybrana liczba nie zawiera się w zbiorze.

Refleksja ….

Refleksje w javie rozumiem jako mechanizm pozwalający na dostęp do pól, konstruktorów oraz metod klasy (nawet tych prywatnych) spoza klasy, czyli coś co tak naprawdę rujnuje moje spojrzenie na jave do tej pory, a przy okazji łamie zasadę enkapsulacjii (musiałem wtrącić jakieś mądre słowo):)

Ważne!!! refleksją możemy używać tylko na już napisanym kodzie. Nie możemy za jej pomocą np dodawać kolejnych pól do klasy.

Enkapsulacja – jedno z założeń programowania obiektowego, polegające na tym, że nie mamy dostępu do pól i metod danej klasy z zewnątrz tej klasy. Chyba, że:

  • dana klasa dziedziczy po klasie
  • pola bądź metody posiadają modyfikator dostępu public.

Dobra wracając do refleksji. W myśl teorii, że nie musimy wiedzieć jak coś dokładnie działa, mamy wiedzieć jak tego użyć to:

Mając przykładową klasę:

public class Car {

private String name;
private String model;
private boolean isPrototype = true;

public Car(){}

public Car(String name, String model) {
this.name = name;
this.model = model;

}


Możemy utworzyć obiekt klasy Car używając konstruktora w następujący sposób:

Car car = Car.class.getConstructor(String.class, String.class).newInstance(„BMW”, „Seria 5”); – Ważne – taki konstruktor musi już istnieć

Aby mieć dostęp do pól klasy używamy klasy Field, czyli:

Field field = Car.class.getDeclaredField("name");
field.setAccessible(true);
field.set(car,"mati");

gdzie:

  • Field field = Car.class.getDeclaredField(„name”) – deklarujemy nazwę pola, w tym przypadku, będziemy mieli dostęp do pola name
  • field.setAccessible(true); – używamy w przypadku pól prywatnych (jeśli pola nie są prywatne, możemy to pominąć)
  • field.set(car,”Audi”); – przekazujemy obiekt który w którym chcemy zmienić wartość pola oraz po przecinku wartość na jaką chcemy zmienić

Aby dostać się do metody danej klasy używamy klasy Method:

Class<?> carClas = Class.forName("pl.marczak.Car");
Car car1 = (Car) carClas.newInstance();
Method setNameMethod = carClas.getDeclaredMethod("setName", String.class);
setNameMethod.setAccessible(true);
setNameMethod.invoke(car1, "Audi");

gdzie:

  • Class<?> carClas = Class.forName(„pl.nazwaPakietu.Car” – tworzymy obiekt klasy Class, musimy podać nazwę klasy wraz z nazwą pakietu w którym się znajduje
  • Car car1 = (Car) carClas.newInstance(); – tworzymy nową instancję (obiekt) klasy Car, używając rzutowania
  • Method setNameMethod = carClas.getDeclaredMethod(„setName”, String.class); – obiekt klasy Method, musimy znać nazwę metody którą chcemy wykorzystać oraz co ta metoda przyjmuje
  • setNameMethod.setAccessible(true); używamy dla metod prywatnych
  • setNameMethod.invoke(car1, „Audi”); użycie metody „setName” z klasy Car poprzez użycie metody invoke na obiekcie klasy Method:) czyli magicznie używamy prywatnej metody z klasy Car, przekazując obiekt na którym chcemy użyć tej metody wraz z argumentem.


Nie napisze Hello World…

Tak jak w nauce programowanie tak i na moim blogu, pierwsze co wypada zrobić to przywitać się niezastąpionym hello worldem. W związku z tym chciałbym serdecznie przywitać wszystkich którzy są tutaj świadomie oraz tych którzy przypadkiem zabłądzili.

A cytując klasyka „Siadamy głęboko w fotelach i zapinamy pasy…” zapraszam do lektury.