August 8, 2010

Logn 2 Dimensional Array Binary Search

By Mohammed Abualrob Algorithms and Data Structures 0 Comments

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");
                }
            }
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

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");

}

8 BIT AVENUE

Logn 2 Dimensional Array Binary Search

More from my site

About Author

Mohammed Abualrob

Add a Comment