2 people like it.

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

More information

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