Search a 2D Matrix

Sizga m x n o'lchamdagi butun sonlardan iborat matrix matritsasi va bitta butun target soni berilgan. Matritsa quyidagi xususiyatlarga ega:

• Har bir qatordagi butun sonlar chapdan o'ngga qarab o'sib borish tartibida joylashgan.
• Har bir qatorning birinchi butun soni undan oldingi qatorning oxirgi butun sonidan katta.

Agar target matritsa ichida mavjud bo'lsa true, aks holda false qaytaring.

Yechimingiz O(log(m * n)) vaqt murakkabligida ishlashi kerak.

func solve(matrix [][]int, target int) bool {
    // ...
}

Misollar

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

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

Input: matrix = [[1]], target = 1
Output: true

Maslahatlar

1. Matritsani qator-ustun sifatida emas, balki bitta uzun saralangan massiv sifatida tasavvur qilib ko'ring — bu binary search qo'llashga imkon beradi.
2. lo=0, hi=rows*cols-1 oralig'ida odatdagi binary search yurgizing; har bir "tekis" mid indeksni mid/cols va mid%cols orqali qator va ustun indeksiga aylantirib, o'sha katakdagi qiymatni target bilan solishtiring.