Dizilerde arama algoritmaları (Searching Algorithms in Arrays) belirli bir öğeyi bulmak için kullanılan sistematik yöntemlerdir. Bu algoritmalar, verilen bir dizinin içinde belirli bir değerin olup olmadığını kontrol etmeye yönelik tasarlanmıştır. Arama işleminin verimliliği, algoritmanın yapısına ve dizinin sıralı olup olmamasına bağlıdır.
Temelde en yaygın kullanılan 3 arama algoritması Doğrusal Arama (Linear Search), İkili Arama (Binary Search) ve İki İşaretçi Tekniği (Two Pointers Technique)'dir. Bu algoritmaların her biri, farklı veri yapılarına ve gereksinimlere göre avantajlar ve dezavantajlar sunar.
Doğrusal Arama (Linear Search)
Doğrusal arama, en basit ve en temel arama algoritmalarından biridir. Bu yöntemde, dizinin ilk elemanından başlanarak aranan öğe bulunana kadar her eleman tek tek kontrol edilir. Eğer öğe dizide bulunursa, ilgili indeks döndürülür; aksi takdirde "bulunamadı" sonucu verilir.
Bu algoritmanın zaman karmaşıklığı O(n) olup, büyük veri kümelerinde verimsiz olabilir. Sırasız diziler için en uygun yöntemlerden biridir.
Doğrusal Arama Adım 1 (Kaynak: www.geeksforgeeks.org)
Doğrusal Arama Adım 3 (Kaynak: www.geeksforgeeks.org)
C++ ile Doğrusal Arama Algoritması Kod Örneği
#includeusing namespace std; int linearSearch(int arr[], int size, int target) { for (int i = 0; i < size; i++) { // sırasıyla bütün dizi dolaşılır. if (arr[i] == target) return i; // Elemanın bulunduğu indeks } return -1; // Eleman bulunamadı } int main() { int arr[] = {10, 20, 30, 40, 50}; int size = sizeof(arr) / sizeof(arr[0]); int target = 30; int result = linearSearch(arr, size, target); if (result != -1) cout << "Eleman bulundu. Indeks: " << result << endl; else cout << "Eleman bulunamadi." << endl; return 0; }
İkili Arama (Binary Search)
İkili arama algoritması, yalnızca sıralı dizilerde çalışan, oldukça verimli bir arama yöntemidir. Bu algoritma tekniğinde dizi sürekli sağ veya sol yarım olacak şekilde ikiye bölünür. Algoritma, dizinin ortasındaki elemanı seçerek aranan değerle karşılaştırır. Eğer aranan değer ortadaki elemandan küçükse sol yarıda, büyükse sağ yarıda aramaya devam edilir. Sürekli ikiye bölünen sonlu bir dizide nihayetinde sağ ve sol değerlerimiz birbirine eşit olacak ve arama sonlanacaktır.
Bu yöntem, O(log n) zaman karmaşıklığına sahiptir ve doğrusal aramaya kıyasla çok daha hızlıdır. Ancak, dizinin sıralı olması zorunluluğu vardır.
İkili Arama Başlangıç Görseli (Kaynak: www.geeksforgeeks.org)
İkili Arama Adım 1 (Kaynak: www.geeksforgeeks.org)
İkili Arama Adım 2 (Kaynak: www.geeksforgeeks.org)
İkili Arama Adım 3 (Kaynak: www.geeksforgeeks.org)
C++ ile İkili Arama Algoritması Kod Örneği
#includeusing namespace std; // İkili Arama Fonksiyonu int binarySearch(int arr[], int left, int right, int target) { while (left <= right) { // Ortanca eleman bulunur int mid = left + (right - left) / 2; // Eğer ortanca eleman hedef değere eşitse, indeksi döndür if (arr[mid] == target) return mid; // Hedef değer ortanca elemandan büyükse, arama dizinin sağ yarısına kaydırılır if (arr[mid] < target) left = mid + 1; else // Hedef değer ortanca elemandan küçükse, arama dizinin sol yarısına kaydırılır right = mid - 1; } return -1; // Eleman bulunamadı } int main() { int arr[] = {10, 20, 30, 40, 50}; int size = sizeof(arr) / sizeof(arr[0]); int target = 30; int result = binarySearch(arr, 0, size - 1, target); if (result != -1) cout << "Eleman bulundu. Indeks: " << result << endl; else cout << "Eleman bulunamadi." << endl; return 0; }
İki İşaretçi Tekniği (Two Pointers Technique)
İki işaretçi tekniği, özellikle sıralı dizilerde belirli bir hedef değere ulaşmak veya belirli bir koşulu sağlamak için kullanılır. Bu yöntemde, dizinin başında ve sonunda olmak üzere iki farklı işaretçi belirlenir. İşaretçiler, belirlenen koşula göre hareket ettirilerek istenilen sonuca ulaşılır.
Örneğin, belirli bir toplamı veren iki elemanı bulmak için bu yöntem kullanılır. İşaretçiler, toplam istenilenden büyükse sağa, küçükse sola kaydırılarak ilerletilir. O(n) zaman karmaşıklığına sahiptir ve büyük veri kümelerinde doğrusal aramaya göre daha verimlidir.
İki İşaretçi Tekniği Adım 1 (Kaynak: www.geeksforgeeks.org)
İki İşaretçi Tekniği Adım 2 (Kaynak: www.geeksforgeeks.org)
İki İşaretçi Tekniği Adım 3 (Kaynak: www.geeksforgeeks.org)
İki İşaretçi Tekniği Adım 4 (Kaynak: www.geeksforgeeks.org)
İki İşaretçi Tekniği Adım 5 (Kaynak: www.geeksforgeeks.org)
İki İşaretçi Tekniği Adım 6 (Kaynak: www.geeksforgeeks.org)
C++ ile İkili İşaretçi Algoritması Kod Örneği
// İki İşaretçi Tekniği C++ Örnek Kod #includeusing namespace std; bool twoPointerSum(int arr[], int size, int target) { int left = 0, right = size - 1; while (left < right) { int sum = arr[left] + arr[right]; if (sum == target) return true; // Çifti bulduk else if (sum < target) left++; // Küçükse sol işaretçiyi sağa kaydır else right--; // Büyükse sağ işaretçiyi sola kaydır } return false; // Çift bulunamadı } int main() { int arr[] = {1, 3, 4, 6, 8, 10}; // Sıralı dizi int size = sizeof(arr) / sizeof(arr[0]); int target = 10; if (twoPointerSum(arr, size, target)) cout << "Toplamı " << target << " olan iki eleman bulundu." << endl; else cout << "Toplamı " << target << " olan iki eleman bulunamadi." << endl; return 0; }
Hangi Algoritma Hangi Koşullarda kullanılmalı?
Dizilerde kullanılan arama algoritmaları, performans açısından farklı avantajlar sunar.
- Doğrusal arama, sırasız diziler için basit ve kolay bir yöntemdir ancak büyük veri kümelerinde verimsizdir.
- İkili arama, sıralı dizilerde oldukça hızlıdır ve büyük veri kümeleri için daha uygundur.
- İki işaretçi tekniği, belirli koşulları sağlayan problemlerde ekstra verimlilik sağlar.
Uygun algoritmanın seçimi, veri yapısının büyüklüğüne, sıralı olup olmamasına ve işlem gereksinimlerine bağlıdır. Optimal performans için en uygun arama algoritmasının belirlenmesi, sistem kaynaklarının etkin kullanımını sağlar.
