Two Dimensional Array Binary Search

Problem

Given a square two dimensional integer array of size (n). Both rows and columns are sorted in ascending order. Write an efficient code to search for a particular element in the array. Assume the array has no duplicates.

Solution

A brute force solution is to loop through the entire array until we find the desired element. The time complexity for this solution is O(n^2). Another solution is to search for the element working on one row at a time using binary search. Binary searching a given sorted row of size (n) takes O(Log(n)) so it would take O(nlog(n)) to search the entire array in worst case. If we are lucky and find the element in the very first row then it would take us only O(log(n)). There could be a O(Log(n)) solution if we can treat the whole array as a single sorted array but the tricky part is how to determine the middle element. I will publish another post for that once I finalize it.

Code

Here is the code in C#

using System;
using System.Collections.Generic;

namespace SortedArray
{
    class Finder
    {
        //Array size
        private int n = 3;

        //Used to save location of the search result
        public int resx = -1;
        public int resy = -1;

        //Two dimensional array
        private int[,] A;

        //Constructor
        public Finder()
        {
            //Sample two dimensional array
            A = new int[3, 3] 
            { 
                { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } 
            };
        }

        //Reset results
        public void Reset()
        {
            resx = -1;
            resy = -1;
        }

        //Find method using brute force
        public bool BruteSearch(int x)
        {
            //Loop through the entire array
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (A[i, j] == x)
                    {
                        //Save result for later access
                        resx = i;
                        resy = j;

                        return true;
                    }
                }
            }

            //If we reach this point then the array
            //does not contain the search key
            return false;
        }

        //This method searches a given row i using
        //binary search. l and r are left and right
        //indices because we are going to call this
        //method recursively. x the is the search key
        public bool BinarySearch(int i, int l, int r, int x)
        {
            //Single element base case
            if (l == r)
            {
                //Element found
                if (x == A[i, l])
                {
                    //Save results
                    resx = i;
                    resy = l;

                    return true;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                //Find the middle element of the given row
                int m = (l + r) / 2;

                //Return if the middle element happens to be
                //the key we are looking for
                if (A[i, m] == x)
                {
                    //Save result
                    resx = i;
                    resy = m;

                    return true;
                }
                //If the key is greater than the middle
                //then search the right half
                else if (x > A[i, m])
                {
                    l = m + 1;
                }
                //Search the left half
                else
                {
                    r = m - 1;
                }

                //Call recursively
                return BinarySearch(i, l, r, x);
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            //Create a finder object
            Finder finder = new Finder();

            //Search for 3 using brute force
            if (finder.BruteSearch(3))
            {
                Console.Out.WriteLine("Element found:");
                Console.Out.WriteLine("Row: " + finder.resx);
                Console.Out.WriteLine("Column: " + finder.resy);
            }
            else
            {
                Console.Out.WriteLine("Element not found");
            }

            //Reset results to start again using
            //a different method
            finder.Reset();
            
            //Binary search each row
            for (int i = 0; i < 3; i++)
            {
                if (finder.BinarySearch(i, 0, 2, 3))
                {
                    Console.Out.WriteLine("Element found:");
                    Console.Out.WriteLine("Row: " + finder.resx);
                    Console.Out.WriteLine("Column: " + finder.resy);
                    return;
                }
            }

            Console.Out.WriteLine("Element not found");
        }
    }
}
Search Terms...

Comments are closed.

%d bloggers like this: