3 people like it.

Binary search

Simple binary search of an array. Tests the array at the middle and divides the search space by half each time it looks for the target item. Returns the target item and how many iterations it took to get there

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 

let rec binSearch target arr =
    match Array.length arr with
      | 0          -> None
      | 1          -> if target = arr.[0] then Some(target) else None
      | _  as ilen -> let middle = ilen / 2
                      match sign <| compare target arr.[middle] with
                        | 0 -> Some(target)
                        | -1 -> binSearch target arr.[..middle-1]
                        | _  -> binSearch target arr.[middle+1..]

binSearch 7918 [|1..10000000|]
val binSearch : target:'a -> arr:'a [] -> 'a option (requires comparison)

Full name: Script.binSearch
val target : 'a (requires comparison)
val arr : 'a [] (requires comparison)
module Array

from Microsoft.FSharp.Collections
val length : array:'T [] -> int

Full name: Microsoft.FSharp.Collections.Array.length
union case Option.None: Option<'T>
union case Option.Some: Value: 'T -> Option<'T>
val ilen : int
val middle : int
val sign : value:'T -> int (requires member get_Sign)

Full name: Microsoft.FSharp.Core.Operators.sign
val compare : e1:'T -> e2:'T -> int (requires comparison)

Full name: Microsoft.FSharp.Core.Operators.compare

More information

Link:http://fssnip.net/ig
Posted:11 years ago
Author:devshorts
Tags: binary search , trees , algorithms

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.