let bs_rotated arr target =
  let lo = ref 0 in
  let hi = ref (Array.length arr - 1) in
  let result = ref (-1) in
  while !lo <= !hi && !result = -1 do
    let mid = (!lo + !hi) / 2 in
    if arr.(mid) = target then result := mid
    else if arr.(!lo) <= arr.(mid) then begin
      if target >= arr.(!lo) && target < arr.(mid) then
        hi := mid - 1
      else
        lo := mid + 1
    end else begin
      if target > arr.(mid) && target <= arr.(!hi) then
        lo := mid + 1
      else
        hi := mid - 1
    end
  done;
  !result

;;

let a = [| 4; 5; 6; 7; 0; 1; 2 |] in
bs_rotated a 0 + bs_rotated a 7 * 10 + bs_rotated a 3 * 100
