Logn 2 Dimensional Array Binary Search

Problem

Given a square two dimensional integer array of size (n). Both rows and columns are sorted in ascending order. Give an algorithm to search for a particular element in the array in O(Log(n)) time complexity. Assume the array has no duplicates.

Solution

This problem is a follow up from the previous post. Modified binary search can be used to search the array in O(Log(n)). The trick is how to calculate the left, middle and right elements. You can refer to the code below for the details.

Code

Here is the code in C#

using System;
using System.Collections.Generic;

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

        //Middle element for binary search
        private int mi = -1;
        private int mj = -1;

        //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[4, 4] 
            {
                {1, 2, 3, 4}, {5, 6, 7, 8}, 
                {9, 10, 11, 12}, {13, 14, 15, 16}
            };
        }

        //This method searches the whole array using
        //binary search. Left and right indices are
        //pairs instead of single values for example
        //left element is (x1, y1) and right element 
        //is (x2, y2). Notice also that rows and columns
        //start at (0)
        public bool Search(int x1, int y1, int x2, int y2, int k)
        {
            //Base case or single element
            if (x1 == x2 && y1 == y2)
            {
                if (k == A[x1, y1])
                {
                    //Save result
                    resx = x1;
                    resy = y1;

                    return true;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                //Applying binary search on a two 
                //dimensional array is almost the 
                //same as that of a one dimensional 
                //array except left and right indices 
                //are now pairs for example (x1, y1) 
                //and (x2, y2). To convert a 2 dimensional 
                //position such as (x1, y1) to a one 
                //dimensional position we apply a simple 
                //formula n * x + y. So we convert the 
                //left pair and the right pair then take 
                //the difference then divide it by 2 in 
                //order to get the distance (d) from the 
                //left pair to the middle pair (mi, mj) 
                //that we are trying to compute
                int d = ((n * x2 + y2) - (n * x1 + y1))/2;

                //Number of elements between the 
                //left pair (x1, y1) and the end 
                //of the row containing (x1, y1)
                int e = n - y1 - 1;

                //The difference (w) between (d) 
                //and (e) represents the number 
                //of elements between the end of 
                //the row containing (x1, y1) and 
                //the right pair (x2, y2)
                int w = d - e;

                //We need to know how many 
                //rows (w) spans
                int r = w / n;

                //We need to know how many 
                //columns (w) spans
                //in row r + 1
                int c = w % n;

                //If (r) is (0) then this means the 
                //middle pair (mi, mj) is on the same 
                //row containing the left pair (x1, y1)
                //so we only add (d) positions to (y1) 
                //to get the (y) coordinate of the middle 
                //pair. The (x) coordinate will be the 
                //same as (x1)
                if (r == 0)
                {
                    mi = x1;
                    mj = y1 + d;
                }
                //Otherwise the middle element is 
                //not on the same row
                else
                {           
                    //When c = 0 this means we need 
                    //to scroll only (r) rows and go 
                    //to the end of the row
                    if (c == 0)
                    {
                        mi = x1 + r;
                        mj = n - 1;
                    }
                    //Otherwise we need to scroll (r) 
                    //rows and (c) columns in row r + 1
                    else
                    {
                        mi = x1 + r + 1;
                        mj = c - 1;
                    }
                }
    
                //Return if the middle element 
                //happens to be the key we are 
                //looking for
                if (A[mi, mj] == k)
                {
                    //Save result
                    resx = mi;
                    resy = mj;

                    return true;
                }
                //If the key is greater than the middle
                //then search the right half
                else if (k > A[mi, mj])
                {
                    //if the middle element (m1, mj) is not 
                    //the last element in the row then (x1, y1) 
                    //will be on the same row as (mi, mj)
                    if (mj < n-1)
                    {
                        x1 = mi;
                        y1 = mj + 1;
                    }
                    //Other wise (x1, y1) will be on the 
                    //begining of the next row 
                    else
                    {
                        x1 = mi + 1;
                        y1 = 0;
                    }
                }
                //Search the left half
                else
                {
                    //If the middle element (mi, mj) is not the 
                    //first element of the row then the right 
                    //element (x2, y2) is on the same row
                    if (mj > 0)
                    {
                        x2 = mi;
                        y2 = mj - 1;
                    }
                    //Otherwise the right element (x2, y2) is on 
                    //the end of the previous row
                    else
                    {
                        x2 = mi - 1;
                        y2 = n - 1;
                    }
                }

                //Call recursively
                return Search(x1, y1, x2, y2, k);
            }
        }
    }

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

            //Search for elements 1 to 17
            for (int i = 1; i <= 17; i++)
            {
                if (finder.Search(0, 0, 3, 3, i))
                {
                    Console.Out.WriteLine("Element found:");
                    Console.Out.WriteLine("Row   : " + finder.resx);
                    Console.Out.WriteLine("Column: " + finder.resy);
                }
                else
                {
                    Console.Out.WriteLine("Element not found");
                }
            }
        }
    }
}
Search Terms...

Comments are closed.

%d bloggers like this: