我想实现递归使用Javascript线性搜索。
Given Array A = [1,2,3,4,5,6]
函数签名 - 是这样的:
LinearSearchRecursively(ArrayGiven, x, startingValue)
如果找到值,则返回否则指数返回-1,但递归地实现它。
将不胜感激,如果你可以将一个正在运行的jsbin或的jsfiddle。
您可以使用数组解构,让您的阵列的头部和尾部做。
那么你应该比较头,如果它等于你的价值,你返回指数到目前为止,否则,你叫同尾和增量索引中的递归函数。
你停止条件是当数组是空的,在这种情况下你返回-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));
你可以改变功能的签名,因为搜索功能的调用应该不考虑初始索引搜索成为可能。
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));
我会做这样的事情:这里是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)}`);
请随意添加。谢谢。