Divide And Conquer Solution For Interviews
IntuitionThis problem is a classic divide and conquer problem! And as with every searching problem, we have to figure out how to narrow our search space.Keep a
# Intuition

This problem is a classic divide and conquer problem! And as with every searching problem, we have to figure out how to narrow our search space.

Keep a pen and paper handy and you will end up with the below diagram after some exploration with the question:

Matrix:
```markdown

  min ..... b ..... c
    .       .       .
    .  II   .   I   . 
    .       .       .
    d .... mid .... f
    .       .       .
    .  III  .   IV  .
    .       .       .
    g ..... h ..... max

Rough Coordinates:
----------------------

- min is (r1, c1)
- mid is (rm, cm)
- max is (r2, c2)
- b   is (r1, cm)
- d   is (rm, c1)
- f   is (rm, c2)
- g   is (r2, c1)
```

- Min and max are the smallest and largest values, respectively 
    - **mid** is not necessarily the average/median/whatever value

- We know that the value at mid is >= all values in quadrant II, and <= all values in quadrant IV.

- We cannot make such claims for quadrants I and III. If we recurse, we can eliminate one quadrant at each level.

Thus, 
- If the target value is less than mid, we must search quadrants I, II, and III. 

- If the target value is greater than mid, we must search quadrants I, III, and IV.


# Complexity

```
Recurrence Relation:  T(n) = 3T(n/2) + O(1) 
```

We're recurring for 3 matrics

- Time complexity: $$Θ(n^{1.585})$$
- Space complexity: $$O(log(max(m,n)))$$

Submission Stats:

- TIME: 163 ms
-  RAM: 24.1 MB

# Code
```python3 []

class Solution:
    def searchMatrix(self, matrix, target) -> int:
        def findBinarySearch(grid, target, r1, c1, r2, c2) -> int:
            if (r1 > r2 or c1 > c2): 
                return False
            
            if (r1 == r2 and c1 == c2 and grid[r1][c1] != target): 
                return False
            
            if (grid[r1][c1] > target): 
                return False
            
            if (grid[r2][c2] < target): 
                return False
            
            # Compute the "mid"
            rm, cm = (r1 + r2) // 2, (c1 + c2) // 2
            
            if (grid[rm][cm] == target): 
                return True
            elif grid[rm][cm] > target:
                return findBinarySearch(grid, target, r1, c1, r2, cm-1) or findBinarySearch(grid, target, r1, cm, rm-1, c2)
            else:
                return findBinarySearch(grid, target, r1, cm+1, rm, c2) or findBinarySearch(grid, target, rm+1, c1, r2, c2)

        return findBinarySearch(matrix, target, 0, 0, len(matrix)-1, len(matrix[0])-1)

```
['Binary Search', 'Divide and Conquer', 'Recursion', 'Python', 'Python3']