0 people like it.

Lower Bound in a sorted array

Returns the index of the first element in the sorted array that does not compare less than 'target'. The given method returns an option type to handling non matching cases. parameters: target - The value whose lower bound has to be found arr - sorted array beg - start index, usually zero en - end index, usually length of array minus one

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

let rec lowerBound target (arr:int64 array) beg en =  
  match sign <| compare en beg with
  | -1 -> None  
  | _ -> let mid = (beg+en)/2
         match  sign <| compare target arr.[mid] with         
         | 1  -> lowerBound target arr (mid+1) en
         | _ -> if beg<mid then
                    lowerBound target arr beg mid
                 else
                    Some(mid)
val lowerBound : target:int64 -> arr:int64 array -> beg:int -> en:int -> int option
val target : int64
val arr : int64 array
Multiple items
val int64 : value:'T -> int64 (requires member op_Explicit)

--------------------
type int64 = System.Int64

--------------------
type int64<'Measure> = int64
type 'T array = 'T []
val beg : int
val en : int
val sign : value:'T -> int (requires member get_Sign)
val compare : e1:'T -> e2:'T -> int (requires comparison)
union case Option.None: Option<'T>
val mid : int
union case Option.Some: Value: 'T -> Option<'T>

More information

Link:http://fssnip.net/805
Posted:3 years ago
Author:Krishna Mohan
Tags: algorithm

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.