Gaza gelme amk bilgisayar mühendisliğinden mezun olanlara bu arabadan vermiolar. Ama orda aldıığın eğitimle kendini zorlarsan bu arabalardan bir tane alabilirsin."
Evet bir üstte gördüğünüz şey benim kendimi motive etme sebebim gençler. Bu tarz bir araba alıp bu tarz arabası olanların yaşadığı bir hayat yaşama hayaliyle bu amk bölümünü okuyorum. yoksa sanırım bırakabilirdim bu bölümü. Neyse
Bu bölümde sizde searching algoritmalarından bahsedicem bahsedebildiğim kadar.
- Linear Search -
Linear search, Türkçesiyle doğrusal arama. Ama siktir edin siz Türkçesini linear search olarak aklınızda kalsın amk.
Arkadaşlar bu linear search adındanda anlaşıldığı gibi bir dizi içinde arama algoritmasıdır.
Bir dizi içersinde bir öğeyi dizinin ilk öğesinden son öğesine kadar teker teker karşılaştırarak arama işlemi yapar Eğer sayıyı bulursa işte fantaziye göre dizideki yerini söyler veya sayının dizi içinde olduğunu söyler veya her ikisinide kullanıcıya geri değer olarak döndürür. Eğer sayımız dizi içinde yoksa yine fantaziye göre bir değer döndürür. Biz -1 değeri döndürücez.
Notasyonu tahmin edeceğiniz gibi O(N)'dir. Yanlış hatırlamıyorsam.
Önemli bir nokta var unutmadan izah edeyim. Linear search genelde dizinin sırasız olduğu durumlarda tercih edilir. Dizinin sıralı olduğu durumlar için daha işe yarar olan binary search'ü kullanırız.
Bi mantık yazalım şuraya
- aranan değeri 'b' değişkeninin içine at
-A[] dizisinin 0. elemanından n.(son) elemanına kadar bir döngüye sok
-A[i] == b , ise değeri döndür
-else -1 değeri döndür.
Kaptınız sanırım işin mantığını ? Birde örnek kod yazalımda iyicene yerine otursun amk.
static int linear(int[] n , int c){
for(int i = 0; i<n.length ; i++){ // işte dizinin boyutu boyunca arıyoruz.
if (n[i]==c) return i; // eğer elemanı bulursa elemanın dizideki yerini döndürüyor.
}
return -1; // bulamazsa -1 değeri döndürüyor.
}
Yapraam linear search kaba taslak bukadar. Çeşitli fantazilere göre değiştirebilirsin tabi. Gelelim diğer searching muhabbetine..
- Binary search -
Öncelikle Şunu aklında çıkarma. Binary search yapacaksan dizindeki elemanlar sıralı olmak zorunda!
Bunu belirttiğime göre gönül rahatlığıyla binary searchden bahsedebilirim artık.
İşin mantığı şu şekilde, Örneğin sözlükten bir kelimenin anlamına bakacaksınız. Sözlükte kelimeler bildiğiniz gibi alfabetik olarak sıralıdır. Bu sebeple kafanıza göre bir sayfa açarsınız sonra kelime hangi harfle başlıyorsa ona göre sayfanızı sağa veya sola çevirirsiniz, nihayetinde kelimenizi bulursunuz.
Algoritmamızın çalışma stilide buna benzerdir. Önce dizinin ortanca sayıdan ikiye böler. Eğer aranan değer ortanca sayıdan küçükse küçük tarafı yine ortadan büyük küçük diye ikiye böler. Sonra yine böler, yine böler ve en sonunda aradığımız elemanı bulur. Eğer aradığımız eleman dizide yoksa. -1 veya kafasına göre bir değer döndürür geriye.
Binary search genelde recursive(kendini çağıran method) algoritmasıdır. bunun recursive kodunu atıcam bu yüzden ama internette while ile yapılanınıda gördüm onuda koyucam nolur nolmaz diye.
Herneyse gelelim örnek koda ;
static int Binary(int[] n , int first, int last, int src){/* Şimdi burda n dizimiz, first dizinin ilk index'i (yani 0), last dizinin son indexi(yani n.lentgh), src ise dizi içinde aradığımız değer */
if ( first <= last){ int middle = (last+first)/2; // burda önce ortadaki indexi buluyoruz haliyle
if (src == n[middle]) { return middle;} /* eğer orta indexin içindeki değer aradığımız değer eşitse,
index değerini geri döndürüyoruz */
else if(src <n[middle]) return Binary(n,first,middle-1,src); /* eğer aradığımız değer ortadaki indexin altında bir sayıysa, orta indexin 1 altındaki değerle methodumuzu tekrar çağırıyoruz(yani dizinin küçük olan yarısına geçiyoruz( bu işlemi bir çok kez tekrar eder eğer çok sayı varsa))*/
else return Binary(n,middle+1,last,src);/*eğer aradığımız değer orta index değerinden büyükse ortadakinin bir fazlasından başlayıp dizinin son indexine kadar olan bölüme geçiyoruz*/
}
return -1; // eğer aradığımız değer yoksa -1 değerini döndürüyoruz.
}
Birde elemanın teki bunu while döngüsü ile yapmış. Onuda atayım belki lazım olur.
Burda bilmediğimiz bir takım kodlar olabilir comparable vs gibi ; Comparable bir super classdır, içinde compareTo gibi methodları barındırır. Bir çeşit sıralama işlemi yapar. İnternetten kullanımını rahatlıkla bulabilirsiniz.
Evet gençler searching algoritmalarımız bu kadardı. Bir sonraki derste görüşmek üzere. Öpüyorum..
Hiç yorum yok:
Yorum Gönder