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: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
let take cnt arr = Seq.toArray (Seq.take cnt arr)

let skipTake cnt arr = 
    let takeAmount = (Array.length arr) - cnt
    let skippedSeq = Seq.skip cnt arr
    Seq.toArray (Seq.take takeAmount skippedSeq)

let binSearch target arr =
    let rec binSearch' target arr count =  
        let middle = (Array.length arr) / 2
        if middle = 0 then
            None
        else
            if target < arr.[middle] then
                binSearch' target (take middle arr) (count + 1)
            else if target > arr.[middle] then
                binSearch' target (skipTake middle arr) (count + 1)
            else 
                Some((target, count))

    binSearch' target arr 0

let search = [|1..10000000|]

// unsafe code, don't use Option.get! could be None...

let (target, iterationsRequired) = Option.get (binSearch 8 search)
val take : cnt:int -> arr:seq<'a> -> 'a []

Full name: Script.take
val cnt : int
val arr : seq<'a>
module Seq

from Microsoft.FSharp.Collections
val toArray : source:seq<'T> -> 'T []

Full name: Microsoft.FSharp.Collections.Seq.toArray
val take : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.take
val skipTake : cnt:int -> arr:'a [] -> 'a []

Full name: Script.skipTake
val arr : 'a []
val takeAmount : int
module Array

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

Full name: Microsoft.FSharp.Collections.Array.length
val skippedSeq : seq<'a>
val skip : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.skip
val binSearch : target:'a -> arr:'a [] -> ('a * int) option (requires comparison)

Full name: Script.binSearch
val target : 'a (requires comparison)
val arr : 'a [] (requires comparison)
val binSearch' : ('b -> 'b [] -> int -> ('b * int) option) (requires comparison)
val target : 'b (requires comparison)
val arr : 'b [] (requires comparison)
val count : int
val middle : int
union case Option.None: Option<'T>
union case Option.Some: Value: 'T -> Option<'T>
val search : int []

Full name: Script.search
val target : int

Full name: Script.target
val iterationsRequired : int

Full name: Script.iterationsRequired
module Option

from Microsoft.FSharp.Core
val get : option:'T option -> 'T

Full name: Microsoft.FSharp.Core.Option.get
Next Version Raw view Test code New version

More information

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