Uptime Robot ratio (30 days)      
v2020.4.156

🚅 Find the closest or exact value using binary search

Before, you want to find the closest or exact value in an array of objects or an array by values, it is important, so that you sort in ascending order, otherwise, it will not work. Example below shows how it works.

The search algorithm is based on https://www.geeksforgeeks.org/find-closest-number-array/ .

If you have a big array, you can use a worker thread as in the code is on the bottom (4 ways to do it / same as in the event loop, but without blocking the event loop.)

Installation 

For NodeJs 

npm install p3x-binary-search-closest

Usage 

Is you have mocha, you can test like this, it has a few use cases (you can see, before I execute this micro-service, I sort the array):

Note: Given npmjs.com has a narrow page, it is better to see the code on https://corifeus.com/binary-search-closest or https://github.com/patrikx3/binary-search-closest

Of course, when using a worker thread, the execution is about 20-25ms longer, then when we are in the event loop, so the worker thread is valid when we are working on a big dataset.

const assert = require('assert');

// for only browser (remove worker thread as is NodeJs Specific)
const bsClosest = require('p3x-binary-search-closest/browser')

// for full blown functions
const bsClosest = require('p3x-binary-search-closest')


describe('binary search closest', () => {

    it('binary search closest by array value, when it is exact match', () => {
        const arr = [6, 9, 8, 4, 1, 7, 3, 10, 5, 2]
        arr.sort()
        const foundValue = bsClosest.byValue(arr, 5)
        assert.ok(foundValue === 5)
    })


    it('binary search closest by array value, when it is not existing, but find the closest value', () => {
        const arr = [9, 8, 4, 1, 7, 3, 10, 5, 2]
        arr.sort()
        const foundValue = bsClosest.byValue(arr, 6)
        assert.ok(foundValue === 7)
    })

    it('binary search closest by array with a property, when it is exact match', () => {
        const arr = [
            {
                id: 4538765,
                value: 9
            },
            {
                id: 4535675,
                value: 10
            },
            {
                id: 4535,
                value: 1
            },
            {
                id: 45654645,
                value: 3
            },
            {
                id: 123123123,
                value: 2
            },
            {
                id: 4532345,
                value: 4
            },
            {
                id: 4545335,
                value: 7
            },
            {
                id: 124535,
                value: 6
            },
            {
                id: 4587635,
                value: 8
            },
        ]
        arr.sort((a, b) => (a.value > b.value) ? 1 : -1)
        const foundValue = bsClosest.byProperty(arr, 7, 'value')
        assert.ok(foundValue.value === 7)
    })


    it('binary search closest by array with a property, but find the closest value', () => {
        const arr = [
            {
                id: 4538765,
                value: 9
            },
            {
                id: 4535675,
                value: 10
            },
            {
                id: 4535,
                value: 1
            },
            {
                id: 45654645,
                value: 3
            },
            {
                id: 123123123,
                value: 2
            },
            {
                id: 4532345,
                value: 4
            },
            {
                id: 4545335,
                value: 7
            },
            {
                id: 124535,
                value: 6
            },
            {
                id: 4587635,
                value: 8
            },
        ]
        arr.sort((a, b) => (a.value > b.value) ? 1 : -1)
        const foundValue = bsClosest.byProperty(arr, 5, 'value')
        assert.ok(foundValue.value === 6)
    })

    it('using thread worker, binary search closest by array value, when it is exact match', async() => {
        const arr = [6, 9, 8, 4, 1, 7, 3, 10, 5, 2]
        arr.sort()
        const foundValue = await bsClosest.worker({
            type: 'value',
            target: 5,
            array: arr,
        })
        assert.ok(foundValue === 5)
    })

    it('using thread worker, binary search closest by array value, but find the closest value', async() => {
        const arr = [9, 8, 4, 1, 7, 3, 10, 5, 2]
        arr.sort()
        const foundValue = await bsClosest.worker({
            type: 'value',
            target: -1,
            array: arr,
        })
        assert.ok(foundValue === 1)
    })


    it('using thread worker, binary search closest by array with a property, when it is exact match', async() => {
        const arr = [
            {
                id: 4538765,
                value: 9
            },
            {
                id: 4535675,
                value: 10
            },
            {
                id: 4535,
                value: 1
            },
            {
                id: 45654645,
                value: 3
            },
            {
                id: 123123123,
                value: 2
            },
            {
                id: 4532345,
                value: 4
            },
            {
                id: 4545335,
                value: 7
            },
            {
                id: 124535,
                value: 6
            },
            {
                id: 4587635,
                value: 8
            },
        ]
        arr.sort((a, b) => (a.value > b.value) ? 1 : -1)
        const foundValue = await bsClosest.worker({
            type: 'property',
            target: 7,
            array: arr,
            property: 'value',
        })
        assert.ok(foundValue.value === 7)
    })


    it('using thread worker, binary search closest by array with a property, but find the closest value', async() => {
        const arr = [
            {
                id: 4538765,
                value: 9
            },
            {
                id: 4535675,
                value: 10
            },
            {
                id: 4535,
                value: 1
            },
            {
                id: 45654645,
                value: 3
            },
            {
                id: 123123123,
                value: 2
            },
            {
                id: 4532345,
                value: 4
            },
            {
                id: 4545335,
                value: 7
            },
            {
                id: 124535,
                value: 6
            },
            {
                id: 4587635,
                value: 8
            },
        ]
        arr.sort((a, b) => (a.value > b.value) ? 1 : -1)
        const foundValue = await bsClosest.worker({
            type: 'property',
            target: 5,
            array: arr,
            property: 'value',
        })
        assert.ok(foundValue.value === 6)
    })
})
p3x Bullet
onenoteGithub onenoteredis-uiGithub redis-uiangular-compileGithub angular-compilegitlistGithub gitlistramdiskGithub ramdiskfreenomGithub freenomopenwrt-insomniaGithub openwrt-insomniadocker-debian-testing-mongodb-stableGithub docker-debian-testing-mongodb-stablecorifeusGithub corifeusredis-ui-serverGithub redis-ui-serversystemd-managerGithub systemd-managerverdaccio-cliGithub verdaccio-clicorifeus-app-web-pagesGithub corifeus-app-web-pagesredis-ui-materialGithub redis-ui-materialxml2jsonGithub xml2jsongrunt-p3x-expressGithub grunt-p3x-expresshtml-pdfGithub html-pdfangular-http-cache-interceptorGithub angular-http-cache-interceptorcorifeus-app-server-patrikx3Github corifeus-app-server-patrikx3corifeus-builderGithub corifeus-builderbinary-search-closestGithub binary-search-closestcorifeus-utilsGithub corifeus-utilsfortune-cookieGithub fortune-cookiejson2xls-worker-threadGithub json2xls-worker-threadcorifeus-builder-angularGithub corifeus-builder-angulartoolsGithub tools