Below, there are two programs:

  • The first program finds a local minimum of an array.
  • The second program finds a local minimum of a matrix.

The local minimum of an array is an index i such that

  • a[i] < a[i-1]
  • a[i] < a[i+1]

The algorithm to find a local minimum of an array is run on the following data sets:

1) A manual test set.

2) A shuffled test set. We shuffle the set to create a permutation of unique N integers. In the majority of cases, only 1 to 5 compares suffice to find the minimum.

3) A decreasing values test set (the worse case scenario). The last value is always the local minimum - zero. The number of compares is lg(N).

using System;
using System.Diagnostics;

// Find the local minimum of an array of N distinct integers.

namespace ConsoleTest
{
    class Program
    {
        private static Stopwatch stopwatch = new Stopwatch();
        private static Random rnd = new Random();
        private static int compares;

        static void Main(string[] args)
        {
            double prev = RunTimeTrial(125);
            for (int N = 250; true; N += N)
            {
                double time = RunTimeTrial(N);
                Console.WriteLine("Size: {0}   Elapsed time: {1:F2} sec   Ratio: {2:F2}\n", N, time, time / prev);
                prev = time;
            }
        }

        static double RunTimeTrial(int N)
        {
            int[] a = new int[N];

            // 1. A manual test set.
            //int[] a = { 8, 9, -1, 3, 4, 1, -3, 2, -2, -4, 0 };
            //N = a.Length;

            // 2. A shuffled test set.
            //for (int i = 0; i < N; ++i)
            //    a[i] = i;
            //Shuffle(a);

            // 3. A decreasing values test set.
            for (int i = 0; i < N; ++i)
                a[i] = i;
            Array.Reverse(a);

            stopwatch.Reset();
            stopwatch.Start();

            compares = 0;

            int index = FindLocalMinimum(a, 0, N - 1);

            Console.WriteLine("Local minimum: a[{0}] = {1}    Compares: {2}    lg(N)={3:F0}", index, a[index], compares, Math.Log(N, 2.0));

            return (stopwatch.ElapsedMilliseconds / 1000.0);
        }

        static int FindLocalMinimum(int[] a, int low, int high)
        {
            compares++;

            int middle = (low + high) / 2;

            // Special cases.
            if (middle == 0) // the local minimum is the first element
                return middle;
            if (middle == high) // the local minimum is the last element
                return middle;

            // Examine the middle value and its two neighbours.
            if (a[middle] < a[middle - 1] && a[middle] < a[middle + 1])
                return middle;

            // Search in the half with the smaller neighbour as it may be the local minimum.
            if (a[middle - 1] < a[middle + 1])
                return FindLocalMinimum(a, low, middle - 1);
            else
                return FindLocalMinimum(a, middle + 1, high);
        }

        // Randomly shuffle the elements in an array.
        static void Shuffle(int[] a)
        {
            int M = a.Length;
            for (int i = 0; i < M; ++i)
            {
                // Exchange a[i] with a random element in a[i..M-1]
                int r = rnd.Next(i, M);
                int tmp = a[i];
                a[i] = a[r];
                a[r] = tmp;
            }
        }
    }
}

The local minimum of a matrix is a pair of indices i and j such that

  • a[i][j] < a[i+1][j]
  • a[i][j] < a[i][j+1]
  • a[i][j] < a[i-1][j]
  • a[i][j] < a[i][j-1]

Test cases:

1) Random elements.

2) The first element is the minimum (the worse case scenario).

3) The last element is the minimum (the worse case scenario).

The worse cases have linear running time i.e. they run in time proportional to N. Note that for large values of N (millions of elements in the array) the running time may deflect from being linear. This is because of memory allocation and deallocation which takes increasingly more time for large N.

using System;
using System.Diagnostics;

// Find the local minimum of a matrix (an N-by-N array of N^2 distinct integers).
// The algorithm runs in time proportional to N.

namespace ConsoleTest
{
    class Program
    {
        private static Stopwatch stopwatch = new Stopwatch();
        private static Random rnd = new Random();

        static void Main(string[] args)
        {
            double prev = RunTimeTrial(125);
            for (int N = 250; true; N += N)
            {
                double time = RunTimeTrial(N);
                Console.WriteLine("Size: {0}   Elapsed time: {1:F2} sec   Ratio: {2:F2}\n", N, time, time / prev);
                prev = time;
            }
        }

        static double RunTimeTrial(int N)
        {
            int[,] a = new int[N, N];

            // 1) Random elements.
            //int n = 1;
            //for (int i = 0; i < N; ++i)
            //    for (int j = 0; j < N; ++j)
            //        a[i, j] = n++;
            //Shuffle(a);

            // 2) The first element is the minimum.
            int n = 1;
            for (int i = 0; i < N; ++i)
                for (int j = 0; j < N; ++j)
                    a[i, j] = n++;

            // 3) The last element is the minimum.
            //int n = 1;
            //for (int i = N-1; i >= 0; --i)
            //    for (int j = N-1; j >= 0; --j)
            //        a[i, j] = n++;


            stopwatch.Reset();
            stopwatch.Start();

            Pair min = FindLocalMinimum(a, N / 2, N / 2); // start in the middle of the matrix

            Console.WriteLine("Local minimum: a[{0},{1}] = {2}", min.RowIndex, min.ColumnIndex, a[min.RowIndex, min.ColumnIndex]);

            return (stopwatch.ElapsedMilliseconds / 1000.0);
        }

        static Pair FindLocalMinimum(int[,] a, int i, int j)
        {
            int min_i, min_j;

            GetMinimum(a, i, j, out min_i, out min_j);

            // This delay is just to simulate some additional work.
            // Thanks to that we can see how the running time grows linearly.
            System.Threading.Thread.Sleep(1);

            if (a[i, j] < a[min_i, min_j])
                return new Pair { RowIndex = i, ColumnIndex = j };
            else
                return FindLocalMinimum(a, min_i, min_j);
        }

        static void GetMinimum(int[,] a, int i, int j, out int min_i, out int min_j)
        {
            int rowCount = a.GetUpperBound(0) + 1;
            int columnCount = a.GetUpperBound(1) + 1;

            // Matrix has only one element.
            if (rowCount == 1 && columnCount == 1)
            {
                min_i = i;
                min_j = j;
            }
            // The tested element is on the boundary of the matrix.
            else if (i == 0 || j == 0 || i == rowCount - 1 || j == columnCount - 1)
            {
                // Left-top corner.
                if (i == 0 && j == 0)
                {
                    if (a[i + 1, j] < a[i, j + 1])
                    {
                        min_i = i + 1;
                        min_j = j;
                    }
                    else
                    {
                        min_i = i;
                        min_j = j + 1;
                    }
                }
                // Right-top corner.
                else if (i == columnCount - 1 && j == 0)
                {
                    if (a[i - 1, j] < a[i, j + 1])
                    {
                        min_i = i - 1;
                        min_j = j;
                    }
                    else
                    {
                        min_i = i;
                        min_j = j + 1;
                    }
                }
                // Left-bottom corner.
                else if (i == 0 && j == rowCount - 1)
                {
                    if (a[i + 1, j] < a[i, j - 1])
                    {
                        min_i = i + 1;
                        min_j = j;
                    }
                    else
                    {
                        min_i = i;
                        min_j = j - 1;
                    }
                }
                // Right-bottom corner.
                else if (i == columnCount - 1 && j == rowCount - 1)
                {
                    if (a[i - 1, j] < a[i, j - 1])
                    {
                        min_i = i - 1;
                        min_j = j;
                    }
                    else
                    {
                        min_i = i;
                        min_j = j - 1;
                    }
                }
                // Top row.
                else if (i == 0)
                {
                    // Get three neighbours of the element and determine which one is the smallest.
                    if (a[i + 1, j] < a[i, j - 1] && a[i + 1, j] < a[i, j + 1]) // test the down neighbour
                    {
                        min_i = i + 1;
                        min_j = j;
                    }
                    else if (a[i, j - 1] < a[i + 1, j] && a[i, j - 1] < a[i, j + 1]) // test the left neighbour
                    {
                        min_i = i;
                        min_j = j - 1;
                    }
                    else if (a[i, j + 1] < a[i + 1, j] && a[i, j + 1] < a[i, j - 1]) // test the right neighbour
                    {
                        min_i = i;
                        min_j = j + 1;
                    }
                    else
                    {
                        throw new ArgumentException("The values in the matrix seems to be not unique.");
                    }
                }
                // Bottom row.
                else if (i == rowCount - 1)
                {
                    // Get three neighbours of the element and determine which one is the smallest.
                    if (a[i - 1, j] < a[i, j - 1] && a[i - 1, j] < a[i, j + 1]) // test the upper neighbour
                    {
                        min_i = i - 1;
                        min_j = j;
                    }
                    else if (a[i, j - 1] < a[i - 1, j] && a[i, j - 1] < a[i, j + 1]) // test the left neighbour
                    {
                        min_i = i;
                        min_j = j - 1;
                    }
                    else if (a[i, j + 1] < a[i - 1, j] && a[i, j + 1] < a[i, j - 1]) // test the right neighbour
                    {
                        min_i = i;
                        min_j = j + 1;
                    }
                    else
                    {
                        throw new ArgumentException("The values in the matrix seems to be not unique.");
                    }
                }
                // Left column.
                else if (j == 0)
                {
                    // Get three neighbours of the element and determine which one is the smallest.
                    if (a[i - 1, j] < a[i + 1, j] && a[i - 1, j] < a[i, j + 1]) // test the upper neighbour
                    {
                        min_i = i - 1;
                        min_j = j;
                    }
                    else if (a[i + 1, j] < a[i - 1, j] && a[i + 1, j] < a[i, j + 1]) // test the down neighbour
                    {
                        min_i = i + 1;
                        min_j = j;
                    }
                    else if (a[i, j + 1] < a[i - 1, j] && a[i, j + 1] < a[i + 1, j]) // test the right neighbour
                    {
                        min_i = i;
                        min_j = j + 1;
                    }
                    else
                    {
                        throw new ArgumentException("The values in the matrix seems to be not unique.");
                    }
                }
                // Right column.
                else if (j == columnCount - 1)
                {
                    // Get four neighbours of the element and determine which one is the smallest.
                    if (a[i - 1, j] < a[i + 1, j] && a[i - 1, j] < a[i, j - 1]) // test the upper neighbour
                    {
                        min_i = i - 1;
                        min_j = j;
                    }
                    else if (a[i + 1, j] < a[i - 1, j] && a[i + 1, j] < a[i, j - 1]) // test the down neighbour
                    {
                        min_i = i + 1;
                        min_j = j;
                    }
                    else if (a[i, j - 1] < a[i - 1, j] && a[i, j - 1] < a[i + 1, j]) // test the left neighbour
                    {
                        min_i = i;
                        min_j = j - 1;
                    }
                    else
                    {
                        throw new ArgumentException("The values in the matrix seems to be not unique.");
                    }
                }
                else
                {
                    throw new ArgumentException("The values in the matrix seems to be not unique.");
                }
            }
            // The tested element is somewhere in the matrix.
            else
            {
                // Get four neighbours of the element and determine which one is the smallest.
                if (a[i - 1, j] < a[i + 1, j] && a[i - 1, j] < a[i, j - 1] && a[i - 1, j] < a[i, j + 1]) // test the upper neighbour
                {
                    min_i = i - 1;
                    min_j = j;
                }
                else if (a[i + 1, j] < a[i - 1, j] && a[i + 1, j] < a[i, j - 1] && a[i + 1, j] < a[i, j + 1]) // test the down neighbour
                {
                    min_i = i + 1;
                    min_j = j;
                }
                else if (a[i, j - 1] < a[i - 1, j] && a[i, j - 1] < a[i + 1, j] && a[i, j - 1] < a[i, j + 1]) // test the left neighbour
                {
                    min_i = i;
                    min_j = j - 1;
                }
                else if (a[i, j + 1] < a[i - 1, j] && a[i, j + 1] < a[i + 1, j] && a[i, j + 1] < a[i, j - 1]) // test the right neighbour
                {
                    min_i = i;
                    min_j = j + 1;
                }
                else
                {
                    throw new ArgumentException("The values in the matrix seems to be not unique.");
                }
            }
        }

        // Randomly shuffle the elements in a two-dimensional array.
        static void Shuffle(int[,] a)
        {
            int rowCount = a.GetUpperBound(0) + 1;
            int columnCount = a.GetUpperBound(1) + 1;

            int M = rowCount * columnCount;
            for (int n = 0; n < M; ++n)
            {
                int i = (n / columnCount);
                int j = (n % columnCount);

                int r = rnd.Next(n, M);

                int ri = (r / columnCount);
                int rj = (r % columnCount);

                // Exchange a[i,j] with a random element in a[i..M-1,j..M-1]
                int tmp = a[i, j];
                a[i, j] = a[ri, rj];
                a[ri, rj] = tmp;
            }
        }

        struct Pair
        {
            public int RowIndex;
            public int ColumnIndex;
        }
    }
}