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

Problem #2 from the book reads: *“write an efficient algorithm that searches for a given element in a 2D array, which elements are sorted by rows and columns, i.e. for each pair of indices i and j elem[i,j] <= elem[i+1,j] and elem[i,j] <= elem[i,j+1]"*.

This problem is known as saddleback search. It has received a lot of attention in the literature. I am not going to dig too dip and will provide a “good enough” solution that allows for further improvement.

My solution would be similarly to Nuts and Bolts problem based upon “divide and conquer” approach.

Let’s begin the search from the lower left corner having the whole 2D array **aa** of **n** columns and **m** rows as the search space. Compare element **aa.[0,m – 1]** with the pattern **x**. If they are equal, our mission is accomplished (we will disregard here that multiple occurences of the pattern may have place). If not and **aa.[0,m – 1] > x**, then we should exclude the last row from search space as elements there just grow towards right side, and move new comparison element one row up. This effectively makes the search space narrower by one row. For the scenario **aa.[0,m – 1] < x** the similar considerations exclude from search space leftmost column moving comparison one element to the right to **aa.[1,m – 1]**. Repeating these actions on the shrinking search space eventually either brings the matched element, or the conclusion that the match does not exist.

F# implementation below is quite literal reproduction of this search strategy description:

let saddlebackSearch (aa: 'a[,]) n m x = let up (h, v) = match v with | 0 -> None | _ -> Some((h, v - 1)) let right (h, v) = match m - 1 - h with | 0 -> None | _ -> Some((h + 1, v)) let rec searcher = function | None -> None | Some(h, v) -> match (Operators.compare aa.[h,v] x) with | 0 -> Some(h, v) | -1 -> searcher (right(h, v)) | _ -> searcher (up(h, v)) searcher (Some((0, m - 1)))

Talking of the effectiveness of the code above is should be clear that it delivers conclusion by time **O(n+m)** in the worst case scenario. Exercising the implementation with the code below

let aa = Array2D.init 10 10 (fun i j -> 3*i + 27*j + j*j) saddlebackSearch aa 10 10 22 saddlebackSearch aa 10 10 175

delivers the following results:

val aa : 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]] val it : (int * int) option = None val it : (int * int) option = Some (5, 5)

## Trackbacks & Pingbacks