提问人：waterically 提问时间：10/20/2022 更新时间：10/20/2022 访问量：81
无法在 Javascript 中使用回调实现二进制搜索函数（如 Array.find）
Can't implement binary search function with callback in Javascript (like a Array.find)
问：
我尝试实现与Array.find相同的函数，但我会在其中使用二进制搜索而不是for-cycle。
我想将回调传递给函数：
binarySearch(elem => elem.value === 4, data)
但是我在实现它时遇到了一个问题：我无法想象我应该用于决定的条件是中间元素形式数组小于或大于回调的值
法典：
let data = [
{value: 1, qwerty: "vika"},
{value: 6, qwerty: "vika"},
{value: -7, qwerty: "vika"},
{value: 14, qwerty: "vika"},
{value: 0, qwerty: "vika"},
{value: 8, qwerty: "vika"},
{value: 6, qwerty: "vika"},
{value: 3, qwerty: "vika"},
{value: -99, qwerty: "vika"},
{value: 99, qwerty: "vika"},
{value: 4, qwerty: "vika"},
]
data.sort((a,b) => a.value-b.value)
function binarySearch(cb, data) {
let middle = data[Math.round(data.length/2)]
let leftPart = data.slice(0, data.length/2)
let rightPart = data.slice(data.length/2, data.length)
if (cb(middle)) { return middle }
else {
return /*CONDITION FOR DECIDE IS MIDDLE LESS OR MORE THAN VALUE FROM CALLBACK*/
? binarySearch(cb, rightPart) : binarySearch(cb, leftPart)
}
}
console.log(binarySearch(elem => elem.value === 4, data))
有没有可能以这种方式实现二叉搜索？
答：
0赞
Portevent
10/20/2022
#1
您需要精确您的病情。您正在寻找 ，但“大于”的值是什么？本能地说.您应该在参数中添加第二个回调，用于评估劣质/优级elem.value === 4elem.value === 4elem.value > 4
binarySearch(equalityCallBack, greaterCallBack, data)
然后
return greaterCallBack(middle)
? binarySearch(equalityCallBack, greaterCallBack, rightPart) : binarySearch(equalityCallBack, greaterCallBack, leftPart)
另类
或者，您可以有一个回调，它返回 1 表示“此值太高”，0 表示“这是正确的值”，-1 表示“此值太低”
function binarySearch(cb, data) {
let middle = data[Math.round(data.length/2)]
let leftPart = data.slice(0, data.length/2)
let rightPart = data.slice(data.length/2, data.length)
if (cb(middle) == 0) { return middle }
else {
return (cb(middle) == 1)
? binarySearch(cb, rightPart) : binarySearch(cb, leftPart)
}
}
function cpr(a, b){
if(a > b) return 1;
if(a < b) return -1;
return 0
}
console.log(binarySearch(elem => cpr(elem, 4), data))
评论
0赞
waterically
10/20/2022
谢谢你，Portevent！我作为您的第二种方式解决了这个问题，但是通过额外的回调第一种方式更不错:)
1赞
gog
10/20/2022
您调用回调两次，这不是一个好主意。另外，最好检查而不是（将回调视为> 0==1obj.prop - targetValue)
0赞
Portevent
10/20/2022
事实上，比 .当然，您可以将回调结果存储在变量中以节省计算。> 0==1
评论