Линейный поиск рекурсивно с использованием Javascript - PullRequest
Новая
       28

Линейный поиск рекурсивно с использованием Javascript

0 голосов
/ 10 февраля 2019

Я пытаюсь реализовать рекурсивный линейный поиск с использованием Javascript. 

Given Array A = [1,2,3,4,5,6]

Подпись функции - что-то вроде этого: 

LinearSearchRecursively(ArrayGiven, x, startingValue)

Если значение найдено, вернуть индекс, иначе вернуть -1, но достигните этого рекурсивно.

Буду признателен, если вы сможете подключить работающий jsbin или jsfiddle.

Ответы [ 3 ]

0 голосов
/ 10 февраля 2019

Вы можете изменить сигнатуру функции, потому что вызов функции поиска должен быть возможен без начального индекса для поиска. 

function linearSearchRecursively(a, x, i = 0) {
    if (i >= a.length) return -1;
    if (a[i] === x) return i;
    return linearSearchRecursively(a, x, i + 1);
}

console.log(linearSearchRecursively([1, 2, 3, 4, 5, 6, 7], 7));
console.log(linearSearchRecursively([1, 2, 3, 4, 5, 6, 7], 9));
console.log(linearSearchRecursively([], 7));

Другим решением может быть использование деструктуризации для массива и проверка по первому элементу. 

function linearSearchRecursively([a, ...rest], x, i = 0) {
    if (a === x) return i;
    if (!rest.length) return -1;
    return linearSearchRecursively(rest, x, i + 1);
}

console.log(linearSearchRecursively([1, 2, 3, 4, 5, 6, 7], 7));
console.log(linearSearchRecursively([1, 2, 3, 4, 5, 6, 7], 9));
console.log(linearSearchRecursively([], 7));
0 голосов
/ 10 февраля 2019

Вы можете сделать это, используя деструктуризацию массива, чтобы получить заголовок и хвост вашего массива.

Затем вы сравниваете голову, если она равна вашему значению, вы возвращаете индекс до сих пор, иначе вывызовите рекурсивную функцию с хвостом и увеличенным индексом.

Ваше условие остановки - когда массив пуст, и в этом случае вы возвращаете -1. ​​

Здесь я оборачиваю рекурсивную функцию и еевызов с внешней функцией, которая имеет более хороший API, без индекса. 

function linearSearch(arr, value) {
  function linearSearchRec(list, idx) {
    if (!list.length) return -1;
    const [head, ...tail] = list;
    if (value === head) return idx;
    else return linearSearchRec(tail, idx + 1);
  }
  return linearSearchRec(arr, 0);
}

console.log(linearSearch([1,2,3,4,5,6], 1));
console.log(linearSearch([1,2,3,4,5,6], 4));
console.log(linearSearch([1,2,3,4,5,6], 10));
0 голосов
/ 10 февраля 2019

Я бы сделал что-то вроде этого: вот ссылка на jsbin:

https://jsbin.com/lijitet/8/edit?js,console

/**
 * Linear Search : Recursion
 * Returns index if found -1 otherwise
 * Procedure LinearSearch(Array A, int x, int i)
 * n = A.length and i is starting position of array
 * if (A[i] === x) return i
 * if (i > n) LinearSearch(A, x, i++)
  * 
  */
 function LinearSearchRecursively(ArrayGiven, x, i) {
     const arrayLength = ArrayGiven.length;

     if (i > (arrayLength - 1)) {
       return -1;
     }
     if(ArrayGiven[i] === x) {
       return i;
     }
     return LinearSearchRecursively(ArrayGiven, x, i+1); 
 }

 // write your test cases here :
 const testArray = [ 1, 2, 3, 4, 5, 6, 7];

 console.log(`Missing Element : ${LinearSearchRecursively(testArray, 7, 0)}`);

Пожалуйста, не стесняйтесь добавлять.спасибо.

...