2D Matrislerde Hedef Aramanın En Etkili Yöntemi: Binary Search

Matris yapılarında arama yaparken genellikle hücre sayısına odaklanıp, matrisin sahip olduğu gizli sıralama özelliğini göz ardı edebiliyoruz. Peki, bir matrisin satırları soldan sağa artan sırada ve her satırın ilk elemanı, bir önceki satırın son elemanından büyükse ne olur? Aslında bu durumda, matrisi tek boyutlu sıralı bir diziye dönüştürmek mümkün hale geliyor. Bu dönüşümle birlikte, standart binary search (ikili arama) yöntemiyle hedef değeri bulmak hem basit hem de son derece verimli bir çözüm sunuyor.

Matrisin Sıralama Özelliğinden Yararlanın

Sıralı bir matrisle karşılaştığınızda, bu matrisi sanki tek bir uzun dizinin parçasıymış gibi düşünebilirsiniz. Örneğin aşağıdaki matrisi ele alalım:

1   3   5   7
10  11  16  20
23  30  34  60

Bu matrisin tüm elemanları soldan sağa ve yukarıdan aşağıya doğru artan sırada yer alıyor. Bu durumda, matrisi şu şekilde tek boyutlu bir dizi olarak hayal edebiliriz:

1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60

Bu özellik, binary search algoritmasını doğrudan uygulamamızı sağlıyor. Ancak buradaki kritik nokta, 2D matrisi 1D diziye dönüştürürken doğru indekslemeyi kullanmak.

Binary Search’ü 2D Matrise Uygulama

Standart binary search algoritmasında, arama aralığını sürekli olarak ikiye bölerek hedef değeri bulmaya çalışırız. 2D bir matrisi bu algoritmaya uyarlamak için, sanal bir indeksleme sistemi kullanıyoruz. Bu sistemde:

• mid değeri, matrisin toplam hücre sayısına göre hesaplanır.
• row = mid / cols formülüyle, sanal indeksin hangi satırda olduğunu belirliyoruz.
• col = mid % cols formülüyleyse, aynı indeksin hangi sütunda yer aldığını buluyoruz.

Örneğin, yukarıdaki matriste toplam 12 hücre bulunuyor. Eğer mid = 6 olarak alınırsa:

row = 6 / 4 = 1
col = 6 % 4 = 2

Bu hesaplama sonucunda, matrix[1][2] konumuna ulaşılıyor ve bu hücredeki değer 16 olarak karşımıza çıkıyor. Bu yöntemle, matrisin herhangi bir hücresine doğrudan erişmek mümkün hale geliyor.

En Verimli Çözüm: Binary Search Uygulaması

Aşağıda, bu yaklaşımı doğrudan kodda uygulayan bir Python örneği yer alıyor. Algoritma, matrisin boyutlarını ve hedef değeri alarak, binary search mantığıyla çalışıyor:

def searchMatrix(matrix: list[list[int]], target: int) -> bool:
    if not matrix or not matrix[0]:
        return False
    
    rows = len(matrix)
    cols = len(matrix[0])
    low, high = 0, rows * cols - 1
    
    while low <= high:
        mid = low + (high - low) // 2
        row = mid // cols
        col = mid % cols
        
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return False

Bu kodda dikkat edilmesi gereken önemli bir detay, arama aralığının kapalı olmasıdır (low <= high). Eğer yanlışlıkla low < high kullanılırsa, algoritma son elemanı atlayarak yanlış sonuçlara yol açabilir. Bu durum, özellikle low ve high değerlerinin eşit olduğu durumlarda ciddi hatalara neden olabilir.

Karmaşıklık Analizi: Neden Bu Yöntem Tercih Edilmeli?

Bu yaklaşımın en büyük avantajı, zaman karmaşıklığının O(log(M×N)) olmasıdır. Bu, matrisin boyutu ne kadar büyük olursa olsun, arama işleminin oldukça hızlı gerçekleşeceği anlamına geliyor. Örneğin, 1000x1000 boyutundaki bir matris için en fazla 20 adımda hedef değeri bulabilirsiniz.

Buna karşılık, brute force yöntemiyle her hücreyi tek tek kontrol etmek, O(M×N) karmaşıklığına sahip oluyor. Bu da özellikle büyük matrislerde performans açısından ciddi bir dezavantaj oluşturuyor.

• Zaman karmaşıklığı: O(log(M×N))
• Uzay karmaşıklığı: O(1)

Mülakatlarda Karşınıza Çıkabilecek Kritik Noktalar

Bu problemi çözerken, mülakatlarda sıkça karşılaşılan bazı yanlış yaklaşımlara dikkat etmek gerekiyor. Bunların başında:

• Arama aralığının yanlış tanımlanması: while (low < high) kullanmak, algoritmanın son elemanı kaçırmasına neden olur.
• Matrisin boş olup olmadığının kontrol edilmemesi: İlk olarak matrisin ve satırların varlığını doğrulamak gerekiyor.
• İndeks hesaplamalarında hata yapılması: row = mid / cols yerine row = mid // cols kullanmak, Python’da float değerler oluşmasına yol açabilir.

Bu tür detaylara dikkat etmek, hem doğru sonuç elde etmenizi hem de mülakatlarda başarılı olmanızı sağlayacaktır.

Sonuç: Matrislerde Arama Yaparken Akıllı Olun

2D matrislerde hedef arama yaparken, matrisin sahip olduğu sıralama özelliklerinden yararlanmak, problemi oldukça basitleştiriyor. Binary search algoritmasını doğru şekilde uyarlamak, hem performans hem de kod okunabilirliği açısından büyük avantajlar sunuyor. Bu yöntemi öğrenerek, sadece bu problemi değil, benzer matris tabanlı problemleri de daha verimli bir şekilde çözebilirsiniz.

Gelecekteki projelerinizde veya mülakatlarınızda karşınıza çıkabilecek bu tür problemler için, matrisin sıralama özelliklerini analiz etmek ve binary search’ü doğru şekilde uygulamak, başarınızın anahtarı olacak.