Doğrusal Arama
Son güncelleme
Doğrusal arama (sıralı arama olarak da bilinir) en basit arama algoritmasıdır: ilk elemandan başlayın ve bir eşleşme bulana veya elemanlar bitene kadar her birini hedefle karşılaştırın. Veri hakkında hiçbir varsayımda bulunmaz — dizi sırasız olabilir ve elemanlar, eşitlik açısından karşılaştırılabilen herhangi bir şey olabilir.
Yukarıdaki animasyon, tarama soldan sağa ilerlerken her karşılaştırmayı vurgular ve hedef göründüğü anda durur. Basitliğinin bedeli hızdır: en kötü durumda her eleman kontrol edilir, bu yüzden O(n) sürede çalışır. Veri sıralıysa ikili arama aynı cevabı O(log n) sürede bulur — önce sıralı veriye ihtiyacınız varsa merge sort sayfasına bakın.
Zaman ve alan karmaşıklığı
| Durum | Karmaşıklık | Notlar |
|---|---|---|
| En iyi durum | O(1) | İlk eleman hedeftir. |
| Ortalama durum | O(n) | Ortalama olarak, bir eşleşmeden önce elemanların yarısı kontrol edilir. |
| En kötü durum | O(n) | Hedef sondadır — veya hiç yoktur. |
| Alan | O(1) | Yalnızca geçerli indeks tutulur. |
Adım adım
| Adım | Ne olur |
|---|---|
| 1 | Dizinin ilk elemanı olan 0. indeksten başlayın. |
| 2 | Geçerli elemanı hedef değerle karşılaştırın. |
| 3 | Eşitlerse geçerli indeksi döndürün — bulundu. |
| 4 | Aksi halde bir konum sağa ilerleyin ve tekrarlayın. |
| 5 | Dizinin sonuna eşleşme olmadan ulaşılırsa hedef mevcut değildir (-1 döndürün). |
Çözümlü örnek
[7, 3, 9, 1, 5, 8, 2] dizisinde 5 aranıyor:
| Karşılaştırma | İndeks | Eleman | Sonuç |
|---|---|---|---|
| 1 | 0 | 7 | 7 ≠ 5 — taramaya devam. |
| 2 | 1 | 3 | 3 ≠ 5 — taramaya devam. |
| 3 | 2 | 9 | 9 ≠ 5 — taramaya devam. |
| 4 | 3 | 1 | 1 ≠ 5 — taramaya devam. |
| 5 | 4 | 5 | 5 = 5 — 4. indekste bulundu. |
Doğrusal arama ne zaman kullanılmalı
| Şu durumlarda kullanın | Şu durumlarda kaçının |
|---|---|
| Veri sırasızsa veya sürekli değişiyorsa | Veri sıralıysa — ikili arama üstel olarak daha hızlıdır |
| Koleksiyon küçükse ve basitlik kazanıyorsa | Veri kümesi büyükse ve tekrar tekrar aranıyorsa |
| Yalnızca sıralı erişiminiz varsa (akışlar, bağlı listeler) | O(1) aramalar için bir indeks veya hash tablosu kurabiliyorsanız |
Linear Search kodu
Python, JavaScript, Java, C++, C, Pseudocode dillerinde temiz ve çalıştırılabilir bir Linear Search uygulaması. Bir dil seçin, kodu kopyalayın veya Coddy Playground'da hazır yüklenmiş olarak açın.
Python ile Linear Search kodu
Python
1def linear_search(a, target):2 # Scan left to right until the target appears3 for i in range(len(a)):4 if a[i] == target:5 return i6 return -17
8
9nums = [7, 3, 9, 1, 5, 8, 2]10print("Index of 5:", linear_search(nums, 5))11print("Index of 4:", linear_search(nums, 4))JavaScript ile Linear Search kodu
JavaScript
1function linearSearch(a, target) {2 // Scan left to right until the target appears3 for (let i = 0; i < a.length; i++) {4 if (a[i] === target) return i;5 }6 return -1;7}8
9const nums = [7, 3, 9, 1, 5, 8, 2];10console.log("Index of 5:", linearSearch(nums, 5));11console.log("Index of 4:", linearSearch(nums, 4));Java ile Linear Search kodu
Java
1public class Main {2 static int linearSearch(int[] a, int target) {3 // Scan left to right until the target appears4 for (int i = 0; i < a.length; i++) {5 if (a[i] == target) return i;6 }7 return -1;8 }9
10 public static void main(String[] args) {11 int[] nums = {7, 3, 9, 1, 5, 8, 2};12 System.out.println("Index of 5: " + linearSearch(nums, 5));13 System.out.println("Index of 4: " + linearSearch(nums, 4));14 }15}C++ ile Linear Search kodu
C++
1#include <iostream>2#include <vector>3
4int linearSearch(const std::vector<int>& a, int target) {5 // Scan left to right until the target appears6 for (std::size_t i = 0; i < a.size(); i++) {7 if (a[i] == target) return static_cast<int>(i);8 }9 return -1;10}11
12int main() {13 std::vector<int> nums = {7, 3, 9, 1, 5, 8, 2};14 std::cout << "Index of 5: " << linearSearch(nums, 5) << "\n";15 std::cout << "Index of 4: " << linearSearch(nums, 4) << "\n";16 return 0;17}C ile Linear Search kodu
C
1#include <stdio.h>2
3int linear_search(const int a[], int n, int target) {4 /* Scan left to right until the target appears */5 for (int i = 0; i < n; i++) {6 if (a[i] == target) return i;7 }8 return -1;9}10
11int main(void) {12 int nums[] = {7, 3, 9, 1, 5, 8, 2};13 int n = sizeof(nums) / sizeof(nums[0]);14 printf("Index of 5: %d\n", linear_search(nums, n, 5));15 printf("Index of 4: %d\n", linear_search(nums, n, 4));16 return 0;17}Pseudocode ile Linear Search kodu
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211
12FUNCTION linearSearch(target : INTEGER) RETURNS INTEGER13 DECLARE i : INTEGER14 // Scan left to right until the target appears15 FOR i ← 1 TO n16 IF nums[i] = target THEN17 RETURN i18 ENDIF19 NEXT i20 RETURN -121ENDFUNCTION22
23OUTPUT "Index of 5 is ", linearSearch(5)24OUTPUT "Index of 4 is ", linearSearch(4)Doğrusal Arama SSS
Doğrusal aramanın zaman karmaşıklığı nedir?
Ortalama ve en kötü durumda
O(n) — tarama her elemanı ziyaret etmek zorunda kalabilir — ve ilk eleman hedef olduğunda en iyi durumda O(1). O(1) ek alan kullanır.Doğrusal arama sıralı veri gerektirir mi?
Hayır — bu onun temel avantajıdır. Doğrusal arama tamamen sırasız veride çalışır, çünkü her elemanı eşitlik açısından kontrol eder; sıranın hiçbir önemi yoktur. Buna karşılık ikili arama yalnızca sıralı dizilerde çalışır.
Doğrusal arama ne zaman ikili aramadan daha iyidir?
Veri sırasızsa ve yalnızca bir kez aranıyorsa (önce sıralamak
O(n log n) tutar), koleksiyon çok küçükse veya akış ya da bağlı liste gibi yalnızca sıralı erişiminiz varsa. Sıralı dizilerde tekrarlanan aramalar için ikili arama kazanır.Doğrusal arama ile sıralı arama aynı şey midir?
Evet — iki isim de aynı algoritmayı tanımlar: hedef bulunana veya koleksiyon bitene kadar elemanları sırayla taramak.
Doğrusal arama ortalama kaç karşılaştırma yapar?
Hedef mevcutsa ve her yerde olma olasılığı eşitse, ortalama yaklaşık
n/2 karşılaştırma; hedef yoksa tam olarak n. Bu doğrusal büyüme, adının doğrusal arama olmasının nedenidir.İlgili kaynaklar
Daha fazla görselleştirme
