Skip to content

If Google would be looking to hire F# programmers – part 6

May 24, 2013

The next problem to be covered in this series is revisiting Part 2 with the goal of further improving performance of search in 2D array. Saddleback search algorithm suggested there is apparently excessive as not fully exploiting the given element order in the 2D search space. The suggested approach would be generalizing binary search algorithm from one-dimension to two.

Let’s illustrate the idea behind the 1D binary search generalization upon 2D with a drawing:

Assume we’ve picked a pivotal element A.[i,j] somewhere in the middle of search space A, which is a m x n matrix, and it came out that A.[i,j] > key, where key is the sought value. Apparently, as all A elements down and to the right of A.[i,j] are no less, than it is, the part of search space colored orange can be safely excluded from further search that should be continued within the part of the search space colored blue. A similar dissecting consideration can be formulated for the case when A.[i,j] < key. The third leftover case is A.[i,j] = key meaning that the sought element has been found.

OK, let’s switch from musing to coding this “divide and conquer” search strategy. The only small leftover decision to make is how to represent irregularly shaped continuation search space. It is easy to notice that it is always a union of two rectangles, so we can use a search function uniformly operating on rectangle areas of A and put them for processing into a stack. Here is the algorithm implementation:

let binarySearch2D key (a: int[,]) =
    let rec searcher (sl: int[,] list) =
        if sl.IsEmpty then false
        else
            let aa = sl.Head
            if aa.Length = 0 then searcher (sl.Tail)
            else
                let pivoth, pivotv = (Array2D.length1 aa)/2, (Array2D.length2 aa)/2 
                if aa.[pivoth, pivotv] > key then
                    searcher (aa.[*,..pivotv-1] :: aa.[..pivoth-1,pivotv..] :: (sl.Tail))
                elif aa.[pivoth, pivotv] < key then
                    searcher (aa.[pivoth+1..,*] :: aa.[..pivoth,pivotv+1..] :: (sl.Tail))
                else true
    searcher [a]

Search per se is performed by inner recursive function searcher defined in line #2, having as argument a stack of rectangular Array2D elements. If it is empty (line #3) means that search for key in the initial matrix a has failed. Otherwise we pop next element (line #5) and, if the element is not empty, dissect it into 4 approximately equal pieces by picking the pivotal element in line #8. Lines #10 and #12 push into the stack remaining search space pieces for search continuation. Thanks to wonderful F# array slicing, expressing required data dissection is a breeze and searcher is always deals with zero-based Array2D pieces.

Let’s wrap up by playing some tests and corner cases:


let a = Array2D.init 10 10 (fun i j -> 3*i + 27*j + j*j)
val a : int [,] = [[0; 28; 58; 90; 124; 160; 198; 238; 280; 324]
[3; 31; 61; 93; 127; 163; 201; 241; 283; 327]
[6; 34; 64; 96; 130; 166; 204; 244; 286; 330]
[9; 37; 67; 99; 133; 169; 207; 247; 289; 333]
[12; 40; 70; 102; 136; 172; 210; 250; 292; 336]
[15; 43; 73; 105; 139; 175; 213; 253; 295; 339]
[18; 46; 76; 108; 142; 178; 216; 256; 298; 342]
[21; 49; 79; 111; 145; 181; 219; 259; 301; 345]
[24; 52; 82; 114; 148; 184; 222; 262; 304; 348]
[27; 55; 85; 117; 151; 187; 225; 265; 307; 351]]
binarySearch2D 73 a
val it : bool = true
binarySearch2D 149 a
val it : bool = false
binarySearch2D -1 a
val it : bool = false
binarySearch2D 400 a
val it : bool = false

To be continued…

Advertisements

From → F#

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: