Gegeven is een \(n \times m\) matrix waarbij elke rij en elke kolom gesorteerd zijn in stijgende volgorde, evenals een waarde \(x\). Gevraagd is te controleren of de waarde \(x\) voorkomt in de matrix.

Ontwerp en implementeer een algoritme voor dit probleem.

Opgave

Schrijf een Python-functie zoekInGesorteerdeTabel(matrix: list, x: int), die een 2-dimensionale array van gehele getallen als argument heeft, alsook een geheel getal \(x\). Voor de 2-dimensionale array geldt dat elke rij en elke kolom gesorteerd zijn in stijgende volgorde. De uitvoer van de methode is True wanneer matrix het element \(x\) bevat en False wanneer matrix het element \(x\) niet bevat.

Voorbeelden

>>> zoekInGesorteerdeTabel([[0, 2], [2, 4]], 2)
True
>>> zoekInGesorteerdeTabel([[1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6], [4, 5, 6, 7]], 7)
True
>>> zoekInGesorteerdeTabel([[1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6], [4, 5, 6, 7]], 4)
True
>>> zoekInGesorteerdeTabel([[1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6], [4, 5, 6, 7]], 8)
False
>>> zoekInGesorteerdeTabel([], 8)
False