Doğrusal dizi arama
Çoğu zaman bir dizide belirli bir değeri bulmanız veya orada olmadığını bildirmeniz gerekir. Bunu yapmak için, dizinin tüm öğelerini ilkinden sonuncusuna kadar incelemeniz gerekir. Verilen X değerine eşit bir eleman bulunur bulunmaz arama sonlandırılmalı ve sonuç görüntülenmelidir. Böyle bir algoritmaya doğrusal
denir.
Bir dizinin maksimum (minimum) öğesini bulmak için doğrusal bir algoritma kullanılır. Bu aynı zamanda bir arama algoritmasıdır. Ancak burada dizinin sonuna gitmek zorunda kalıyoruz, çünkü tüm elemanları mevcut maksimum (minimum) değerle karşılaştırmak ve mevcut eleman maksimum (minimum) değerden büyük (küçük) ise maksimum (minimum) değeri değiştirin.
|
Bu sorunu çözmek için başka bir yaklaşım mümkündür. Gerekli değer bulunursa döngüden erken çıkış kullanabilirsiniz.
C++'da break deyimi bir döngüden çıkmak için kullanılır;
|
önce
{
-ms-user-select: yok;
-moz-user-select: yok;
-webkit-user-select: yok;
kullanıcı seçimi: yok; }
İkili Arama
İkili (veya ikili) arama verimli bir arama algoritmasıdır ve doğrusal aramadan daha hızlıdır. Örneğin 1024 elemanlı bir dizi için en kötü durumda (istenen eleman dizide yokken) bir lineer arama 1024 elemanın tamamını işleyecektir fakat ikili arama ile 10 elemanı işlemek yeterlidir. Bu sonuç, döngünün ilk adımından sonra arama alanının 512 öğeye, ikinci adımdan sonra 512 öğeye kadar daralması nedeniyle elde edilir. 256'ya kadar vs.
Böyle bir algoritmanın dezavantajları, veri sıralama gereksiniminin yanı sıra herhangi bir veri öğesine sabit (veri miktarından bağımsız) bir süre içinde erişebilme yeteneğidir. Bu nedenle algoritma sırasız dizilerde çalışamaz.
Algoritma
- Orta öğeyi
A[c] seçin ve X ile karşılaştırın.
- Eğer
X = A[c] ise bulundu (dur).
- Eğer
X < A[c], ilk yarıda daha fazla arama yapın.
- Eğer
X > A[c] ise, ikinci yarıya daha yakından bakın.
Uygulama
L = 0; R=N; // başlangıç bölümü
iken ( L < R - 1)
{
c = (Sol + Sağ) / 2; // ortasını bulduk
if ( X < A[c] ) // segment sıkıştırma
R=c;
başka
L = c;
}
eğer ( A[L] == X)
cout
nerede:
A - kaynak dizisi,
N - dizi boyutu,
X - aranan numara,
Diğer uygulamalar mümkündür.
Örneğin, döngüden erken çıkış kullanmak
L = 0; R = N - 1;
iken (R >= L)
{
c = (Sol + Sağ) / 2;
eğer ( X == A[c] )
{
nX = c;
kırmak;
}
eğer (X < A[c]) R = orta - 1;
eğer (X > A[c]) L = orta + 1 ise;
}
eğer ( nX < 0)
cout
|
Doğrusal ve ikili arama algoritmalarının karşılaştırma sayısına göre karşılaştırılması
Örnekler
| # |
Satır Arama |
İkili arama |
| 2 |
2 |
2 |
| 16 |
16 |
5 |
| 1024 |
1024 |
11 |
| 1048576 |
1048576 |
21 |
İkili sıralamanın avantajı daha hızlı olmasıdır.
Eksileri- önceden sıralanmış bir dizi gereklidir.
|