Can't implement binary search function with callback in Javascript (like a Array.find)-CodePudding

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))