August 6, 2010
HomeAlgorithms and Data StructuresTwo Dimensional Array Binary Search

Two Dimensional Array Binary Search

By  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. 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#

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
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");
        }
    }
}

More from my site

Tags:, , ,

About Author

Mohammed Abualrob

Software Engineer @ Cisco

Add a Comment

Your email address will not be published. Required fields are marked *