Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
(*
* Performs a binary search on the cumulative sums of lengths.
* and return a tuple as (minBound, maxBound)
* : arr: int[] -> n: int -> (int,int)
*)
let getBounds a (n:int): int*int =
let binarySearch (arr:int[]) (n:int) : (int*int) =
let rec binarySearch' (arr:int[]) (n:int) (low:int) (high:int) =
if arr.[high] < n then
(high, System.Int32.MaxValue)
else if high - low <= 1 then
if arr.[low] = n then
(low, low)
else
(low,high)
else
let mid = (high + low)/2
match arr.[mid],n with
| (a,b) when a <= b-> binarySearch' arr n mid high
| _ -> binarySearch' arr n low mid
binarySearch' arr n 0 (arr.Length-1)
binarySearch a n
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment