Leetcode 74 Search a 2D Matrix

Soru

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row.

Örnek 1

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Örnek 2

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Çözüm

• Bir matriste belirli bir hedef sayıyı ikili arama yöntemi ile bulmanızı ister. Bu matris özel bir yapıya sahiptir: her satır sıralıdır ve bir sonraki satırın ilk elemanı bir önceki satırın son elemanından büyük veya eşittir. Bu özellikler, matrisi tek boyutlu bir dizi gibi düşünerek ikili arama yapmayı mümkün kılar.
• Girdi: İki boyutlu bir tam sayı matrisi matrix ve bir hedef sayı target.
• Çıktı: Eğer target matriste varsa true, yoksa false döndür.
• Bu problem, matrisin düz bir dizi gibi ele alınabileceği ve buna göre ikili arama yapılacağı anlamına gelir. Matris elemanlarına doğrudan indeks hesaplayarak erişebilirsiniz, böylece iki boyutlu bir yapının tek boyutluymuş gibi ele alınmasını sağlayabilirsiniz.
• Çalışma Mekanizması:
• Başlangıç ve Bitiş İşaretçileri: left ve right işaretçileri matrisin başlangıç ve bitiş noktalarını belirler.
• Ortanca Değerin Hesaplanması: İkili arama yapılırken mid değeri hesaplanır ve bu değer, matrisin bir boyutlu bir diziymiş gibi ele alınarak mid_value değerine çevrilir.
• Karşılaştırma ve İşaretçilerin Güncellenmesi: Eğer mid_value, hedefe eşitse true döndürülür. Eğer hedef mid_value’den büyükse, arama alanı sağa kaydırılır; eğer küçükse sola kaydırılır.
• Sonuç: Eğer left işaretçisi right işaretçisini geçerse, hedef değer matriste bulunamamış demektir ve false döndürülür.

Code

class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix:
            return False
        
        rows, cols = len(matrix), len(matrix[0])
        left, right = 0, rows * cols - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            mid_value = matrix[mid // cols][mid % cols]  # Satır ve sütun indekslerini hesapla
            
            if mid_value == target:
                return True
            elif mid_value < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return False

        
        

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(log(mn)), burada m satır sayısı ve n sütun sayısıdır. Matris, tek boyutlu bir diziymiş gibi ele alındığı için tüm elemanlar üzerinde logaritmik zamanda arama yapılır.
• Space complexity (Alan Karmaşıklığı) : O(1), çünkü ekstra alan kullanılmaz; tüm işlemler mevcut matris üzerinde gerçekleştirilir.