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

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

## Trackbacks & Pingbacks