/*

  Binary search in Picat.

  From http://rosettacode.org/wiki/Binary_search
  """
  Given the starting point of a range, the ending point of a range, and the 
  "secret value", implement a binary search through a sorted integer array 
  for a certain number. Implementations can be recursive or iterative 
  (both if you can). Print out whether or not the number was in the array 
  afterwards. If it was, print the index also. The algorithms are as such 
  (from the wikipedia): 
  """

  Also see http://en.wikipedia.org/wiki/Binary_search

  Model created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

main => go.

go =>
  A = [2, 4, 6, 8, 9],
  println(A),
  % println(binary_search(A, 2)),

  test1(A,2),
  test1(A, 1),
  test1(A, 8),
  test1(A, 10),
  test1(A, 9),
  test1(A, 5),

  test1([1,20,3,4], 5), % not sorted array

  println("recursive:"),
  % println(binary_search2(A, 2)),
  test2(A,2),
  test2(A, 1),
  test2(A, 8),
  test2(A, 10),
  test2(A, 9),
  test2(A, 5),

  test2([1,20,3,4], 5), % not sorted array


  nl.

test1(A, Value) =>
  Ret = binary_search(A,Value),
  printf("A: %w Value:%d Ret: %d: ", A, Value, Ret),
  if Ret == -1 then
    println("The array is not sorted.")
  elseif Ret == 0 then
    printf("The value %d is not in the array.\n", Value)
  else
    printf("The value %d is found at position %d.\n", Value, Ret)
  end.


test2(A, Value) =>
  Ret = binary_search_rec(A,Value),
  printf("A: %w Value:%d Ret: %d: ", A, Value, Ret),
  if Ret == -1 then
    println("The array is not sorted.")
  elseif Ret == 0 then
    printf("The value %d is not in the array.\n", Value)
  else
    printf("The value %d is found at position %d.\n", Value, Ret)
  end.


%
% iterative version
%
binary_search(A, Value) = V =>
  V1 = 0,
  % we want a sorted array
  if not sort(A) == A then
    V1 := -1
  else 
    Low = 1,
    High = A.length,
    Mid = 1,
    Found = 0,
    while (Found == 0, Low <= High) 
       Mid := (Low + High) // 2,
       if A[Mid] > Value then
         High := Mid - 1
       elseif A[Mid] < Value then
         Low := Mid + 1
       else 
         V1 := Mid,
         Found := 1
      end
    end
  end,

  V = V1.



% Recursive version
binary_search_rec(A, Value) = Ret =>
   Ret = binary_search_rec(A,Value, 1, A.length).

binary_search_rec(A, _Value, _Low, _High) = -1, sort(A) != A => true.
binary_search_rec(_A, _Value, Low, High)  =  0, High < Low   => true.
binary_search_rec(A, Value, Low, High)    = Mid => 
   Mid1 = (Low + High) // 2,
   if A[Mid1] > Value then
      Mid1 := binary_search_rec(A, Value, Low, Mid1-1)
   elseif A[Mid1] < Value then
      Mid1 := binary_search_rec(A, Value, Mid1+1, High)
   end,
   Mid = Mid1.