2 people like it.
Like the snippet!

Binary search on sorted arrays

Performs binary search on sorted arrays. Both ascending and descending-ordered arrays are supported. Pass a reverse comparer to the tryBinarySearchWith function to search on descending-ordered arrays.

Implementation

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15:

module Array =
    let tryBinarySearchWith comparer (value: 'a) (source: 'a[]) =
        let rec loop lo hi =
            if lo > hi then None
            else
                let mid = lo + (hi - lo) / 2
                match sign <| comparer value source.[mid] with
                | 0 -> Some mid
                | 1 -> loop (mid + 1) hi
                | _ -> loop lo (mid - 1)

        loop 0 (source.Length - 1)

    let tryBinarySearch value source =
        source |> tryBinarySearchWith compare value

Examples

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16:

let source1 = [|1 .. 100|]
match source1 |> Array.tryBinarySearch 42 with
| Some index -> printfn "Found at index %d" index
| None -> printfn "Nope!"

let reverseCompare a b = compare b a
let source2 = source1 |> Array.sortWith reverseCompare
match source2 |> Array.tryBinarySearchWith reverseCompare 42 with
| Some index -> printfn "Found at index %d" index
| None -> printfn "Nope!"

(*
Result:
Found at index 41
Found at index 58
*)

module Array

from Microsoft.FSharp.Collections

val tryBinarySearchWith : comparer:('a -> 'a -> int) -> value:'a -> source:'a [] -> int option

Full name: Script.Array.tryBinarySearchWith

val comparer : ('a -> 'a -> int)

val value : 'a

val source : 'a []

val loop : (int -> int -> int option)

val lo : int

val hi : int

union case Option.None: Option<'T>

val mid : int

val sign : value:'T -> int (requires member get_Sign)

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

union case Option.Some: Value: 'T -> Option<'T>

property System.Array.Length: int

val tryBinarySearch : value:'a -> source:'a [] -> int option (requires comparison)

Full name: Script.Array.tryBinarySearch

val value : 'a (requires comparison)

val source : 'a [] (requires comparison)

val compare : e1:'T -> e2:'T -> int (requires comparison)

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

val source1 : int []

Full name: Script.source1

Multiple items
module Array

from Script

--------------------
module Array

from Microsoft.FSharp.Collections

val index : int

val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn

val reverseCompare : a:'a -> b:'a -> int (requires comparison)

Full name: Script.reverseCompare

val a : 'a (requires comparison)

val b : 'a (requires comparison)

val source2 : int []

Full name: Script.source2

val sortWith : comparer:('T -> 'T -> int) -> array:'T [] -> 'T []

Full name: Microsoft.FSharp.Collections.Array.sortWith

Previous Version Raw view Test code New version

More information

Link:	http://fssnip.net/7WW
Posted:	5 years ago
Author:	Bang Jun-young
Tags:	array , binary search