search

const fs = require('fs');

const buildStepCounter = (step = 1) => () => step++

list = [9,10,14,15,17,19,24,24,26,28,29,31,33,33,42,42,47,47,58,59,61]
node = 47
let result = ''

const linearSearch = (node, list) => {
  let resultIndex;
  for (index=0; index < list.length; index++){
    result += `${stepCounter()}) Устанавливаем значение индекса равным ${index}\n`
    result += `${stepCounter()}) Сравниваем элемент массив[индекс] и искомое значение\n`
    if (list[index] == node) {
      result += `${stepCounter()}) Запоминаем значение индекса\n`
      resultIndex = index
    }
    result += `${stepCounter()}) Возвращаемся в начало цикла\n`
  }
  result += `${stepCounter()}) Выводим последнее запомненое значение индекса равное ${resultIndex}\n`
};

const binarySearch = (node, list, start, end) => {
  const middle = Math.floor((start + (end - start)/2));
  result += `${stepCounter()}) Проверяем массив от ${start} до ${end}. Средний индекс ${middle}\n`
  result += `${stepCounter()}) Проверяем условие конечный индекс == начальный индекс < 2\n`
  if (end == start) {
    result += `${stepCounter()}) Так как условие выполнено, рекурсия окончена - выводим начальный индекс равный ${start}\n`
    return start
  } else {
    result += `${stepCounter()}) Так как условие не выполнено, проверяем условие массив[срединый индекс] > искомый элемент\n`
    if (list[middle] > node) {
      result += `${stepCounter()}) Так как условие выполнено, вызовем поиск(искомый элемент, массив, середина+1, конец)\n`
      return binarySearch(node, list, middle + 1, end)
    } else {
      result += `${stepCounter()}) Так как условие выполнено, вызовем поиск(искомый элемент, массив, начало, середина)\n`
      return binarySearch(node, list, start, middle)
    }
  }
}


const fibSearch = (node, list) => {
  const fib = n => {
    return n <= 1 ? n : fib(n - 1) + fib(n - 2);
  }

  let currentFibNumber = 2

  while (true) {
    result += `${stepCounter()}) Число Фибоначчи = ${fib(currentFibNumber)}\n`
    let end
    result += `${stepCounter()}) Сравниваем число Фибоначчи и длину массива\n`
    if (fib(currentFibNumber) < list.length -1) {
      end = fib(currentFibNumber)
    } else {
      end = list.length - 1
      result += `${stepCounter()}) Так как длина массива больше чем число Фибоначчи, то вместо числа Фибонначи возьмем длину массива ${end}\n`
    }

    result += `${stepCounter()}) Сравниваем элемент под номером ${end} и искомый элемент\n`
    if (list[end] > node) {
      let res;
      result += `${stepCounter()}) Проводим перебор с ${fib(currentFibNumber - 1)} до ${end}\n`
      for (i = fib(currentFibNumber - 1); i <= list[end]; i++) {
        if (list[i] == node) {
          res = i;
        }
      }
      result += `${stepCounter()}) Выводим индекс найденного элемента ${res}\n`
      return res;
    }
    result += `${stepCounter()}) Возвращаемся в начало цикла\n`
    currentFibNumber++
  } 
}

let stepCounter = buildStepCounter()
linearSearch(node, list)
fs.writeFileSync("linear.txt", result)

result = ''
stepCounter = buildStepCounter()
binarySearch(node, list, 0, list.length-1)
fs.writeFileSync("binary.txt", result)

result = ''
stepCounter = buildStepCounter()
fibSearch(node, list)
fs.writeFileSync("fib.txt", result)