Четвёртая неделя курса Algorithmic Toolbox началась с изучения принципа "разделяй и властвуй" на примере бинарного поиска в отсортированном массиве. А я вслед за лекторами попробовал сделать свою реализацию этого алгоритма на OCaml.

Вообще лектор честно предупреждает, что несмотря на всю рекурсивную природу принципа "разделяй и властвуй" рекурсивная реализация может быть более затратной из-за стека. Делай я это на Python, то так бы оно и было, но в OCaml у меня есть хвостовая рекурсия, которой я и хочу воспользоваться.

Работать алгоритм будет примерно так, как описано в лекции. Если искомые элемент есть, то возвращается его индекс, если его нет, то максимальный индекс, где data[i] < key, если key < data[low], то результат low - 1.

Цель, как и прежде, не столько в эталонной реализации алгоритмов, сколько практика программирования на OCaml. Поэтому вводные условия такие.

• на вход программе поиска через stdin - отсортированный список целых чисел;
• на выход - индекс;
• проверяющая программа - тоже на OCaml;
• реализация алгоритма в проверяющей программе - линейный поиск в отсортированном массиве;
• если нужно, то можно использовать Core.Std (жаль, что она недоступна на codingame).

open Core.Std


let rec binary_search data low high key =
    if Array.length data = 0 || high < low then
        (low - 1)
    else
        let middle = low + (high - low) / 2 in
        if key = data.(middle) then
            middle
        else if key < data.(middle) then
            binary_search data low (middle - 1) key
        else
            binary_search data (middle + 1) high key


let () =
    let data =
        match In_channel.input_line In_channel.stdin with
        | Some "" -> [||]
        | Some line -> String.split line ' ' |> List.map ~f:int_of_string |> Array.of_list
        | None -> invalid_arg "You should input sorted array"
    in
    let key =
        input_line stdin |> int_of_string
    in

    binary_search data 0 ((Array.length data) - 1) key |> string_of_int |> print_endline;

Теперь нужно написать программу, которая запустит эту, как внешний процесс, отдаст данные на вход, получит результат и сравнит со своим вариантом. Получилась вот такая программа:

open Core.Std


let search data key =
    if Array.length data = 0 || key < data.(0) then
        -1
    else if key > data.((Array.length data) - 1) then
        Array.length data - 1
    else
        let rec _search _data i =
            if _data.(i) = key then
                i
            else if _data.(i) < key then
                _search _data (i + 1)
            else
                i - 1
        in
        _search data 0


let () =
    let rec gen = function
        | 0 -> []
        | num -> Random.int 10 :: gen (num - 1)
    in

    let create_test_data length =
        List.sort (gen length) ~cmp:compare |> Array.of_list, Random.int 10
    in

    let prepare numbers key =
        (String.concat_array ~sep:" " (Array.map numbers ~f:string_of_int)) ^ "\n", string_of_int key ^ "\n"
    in

    let path = Unix.getcwd () ^ "/" ^ "binary_search.ml.byte" in

    let run_process numbers_line key_line =
        let procin, procout = Unix.open_process path in
        Out_channel.output_string procout numbers_line;
        Out_channel.output_string procout key_line;
        Out_channel.flush procout;

        let result = match In_channel.input_line procin with
        | None -> invalid_arg "Broken channel"
        | Some line -> int_of_string line
        in

        Unix.close_process (procin, procout);

        result
    in

    let check numbers key linear_result binary_result =
        (
            (linear_result = binary_result) ||
            (
                linear_result < Array.length numbers &&
                binary_result < Array.length numbers &&
                numbers.(linear_result) = numbers.(binary_result)
            )
        )
    in

    let print_state linear_result binary_result numbers key =
        printf " linear_result: %d\n" linear_result;
        printf " binary_result: %d\n" binary_result;
        printf " data: %s\n" (String.concat_array ~sep:" " (Array.map numbers ~f:string_of_int));
        printf " key: %d\n" key;
        printf " -----------\n\n";
        printf "%!";
    in

    for i = 0 to 100 do
        let numbers, key = create_test_data i in
        let numbers_line, key_line = prepare numbers key in
        let binary_result = run_process numbers_line key_line in

        let linear_result = search numbers key in

        if not (check numbers key linear_result binary_result) then begin
            printf "Error:\n";
            print_state linear_result binary_result numbers key;
        end
    done;

    printf "Done\n"

Из-за немного разного принципа работы поиска, пришлось проверять не только найденные индексы, а ещё и равенство чисел по этим индексам, если они разные. Собственно, в лекции тоже упоминается этот случай и обе позиции считаются удовлетворяющими условию.

Нужно бы ещё проверить результат Unix.close_process, но не в этот раз.