3 people like it.
Like the snippet!

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