# Example of Binary Search

## Element Search Algorithm in the Sorted Matrix of Size NxN

To find the desired item we can use a binary search for each line. The algorithm requires `O (M log (N))` time as it is necessary to process the `M` columns, for each of which we spend `O (log (N))` time. We will analyze this method.

Let’s take a look at the example: Let’s ask ourselves: where can the elements be?

We know that all the rows and columns are sorted. It means that the element `[i] [j]` is greater than the elements in row `i` lying between 0 and `j` column and `j` row elements between lines 0 and `i-1`.

In other words:

```a[i] <= a[i] <= ... <= a[i][j-i] <= a[i][j]
a[j] <= a[j] <= ... <= a[i-1][j] <= a[i][j]
```

Let’s look at the matrix: The element, which is in dark gray cell, is greater than the other selected elements. White cell elements are sorted. Each of them is more like a left element and an element located above. Thus, the highlighted item is bigger than the elements in the square. It is possible to formulate a rule: the lower right corner of any rectangle selected in the matrix will contain the largest element.

Similarly, the upper left corner is always the smallest. The colors in the diagram below reflects information about ordering elements (light gray<white<dark gray): Let’s go back to the original problem. Let us assume that we need to find the element 85. If we look at the diagonal, we see the elements 35 and 95. What kind of information on the location of the element 85 can be learned? 85 can not be in the dark gray area since the element 95 located in the upper left corner is the smallest element in this square. 85 can not belong to the light gray area, as the element 35 is in the lower right corner. 85 should be in one of the two white areas.

Thus, we divide our grid into four quadrants and search in the lower left and upper right quadrants. They can also be divided into quadrants, and the search can be continued.

Note that the diagonal is sorted, which means that we can effectively use binary search.