Uva10706.fsx

(*
 * 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