I try to implement function that the same is Array.find, but I would use binary search in it instead of for-cycle.
I want to pass callback to the function:
binarySearch(elem => elem.value === 4, data)
But i faced an issue when implemented it: I cant imagine condition I should use for decide is middle element form array less or more than value from callback
Code:
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))
Is it even possible to implement binary search in this way?
CodePudding user response:
You need to precise your condition. You are looking for elem.value === 4
, but what are values "greater" thanelem.value === 4
? Instinctively, we can say elem.value > 4
. You should add a second callback in your parameter, for evaluating inferior / superior
binarySearch(equalityCallBack, greaterCallBack, data)
And then
return greaterCallBack(middle)
? binarySearch(equalityCallBack, greaterCallBack, rightPart) : binarySearch(equalityCallBack, greaterCallBack, leftPart)
Alternative
Or you can have one callBack, that returns 1 for "this value is too high", 0 for "this is the correct value" and -1 for "this value is too low"
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))