Searching and sorting in a 2-d array

Suppose you have a 2-d array with integers sorted both horizontally and vertically.
a) Search for the occurrence of a value in the array
b) Sort the array into a single-dimensional array

Find the number of negative elements in most efficient way

Given an n X n array with rows sorted and cols sorted, find the number of negative elements in most efficient way.