.github/000077500000000000000000000000001516076774300124365ustar00rootroot00000000000000.github/workflows/000077500000000000000000000000001516076774300144735ustar00rootroot00000000000000.github/workflows/build.yml000066400000000000000000000016761516076774300163270ustar00rootroot00000000000000# This workflow will do a clean install of node dependencies, build the source code and run tests across different versions of node # For more information see: https://help.github.com/actions/language-and-framework-guides/using-nodejs-with-github-actions name: build on: schedule: - cron: '0 0 1 * *' push: branches: [ master ] pull_request: branches: [ master ] jobs: build: runs-on: ubuntu-latest strategy: matrix: node-version: ['lts/*'] # See supported Node.js release schedule at https://nodejs.org/en/about/releases/ steps: - uses: actions/checkout@v2 - name: Use Node.js ${{ matrix.node-version }} uses: actions/setup-node@v2 with: node-version: ${{ matrix.node-version }} - run: npm i -g grunt-cli - run: npm install - run: grunt .gitignore000066400000000000000000000003511516076774300130650ustar00rootroot00000000000000/build /node_modules /*.log /*.iws .idea/workspace.xml .idea/tasks.xml .idea/profiles_settings.xml .idea/inspectionProfiles/Project_Default.xml .idea/inspectionProfiles/profiles_settings.xml node_modules/.yarn-integrity .nyc_output .npmignore000066400000000000000000000002711516076774300130750ustar00rootroot00000000000000/.idea /artifacts /build /Gemfile /_layouts /_site /_includes /test /node_modules /*.iml /*.ipr /*.iws /.travis.yml /.scrutinizer.yml /Gruntfile.js /corifeus-boot.json /.github /.vscodeGruntfile.js000066400000000000000000000005261516076774300133760ustar00rootroot00000000000000const utils = require('corifeus-utils'); module.exports = (grunt) => { const builder = require(`corifeus-builder`); const loader = new builder.loader(grunt); loader.js({ replacer: { type: 'p3x', npmio: true, }, }); grunt.registerTask('default', builder.config.task.build.js); } LICENSE000066400000000000000000000023561516076774300121110ustar00rootroot00000000000000 @license p3x-binary-search-closest v2024.4.104 🚅 Find the closest or exact value using binary search https://corifeus.com/binary-search-closest Copyright (c) 2024 Patrik Laszlo / P3X / Corifeus and contributors. MIT License Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. README.md000066400000000000000000000223111516076774300123540ustar00rootroot00000000000000[//]: #@corifeus-header [![NPM](https://nodei.co/npm-dl/p3x-binary-search-closest.png?downloads=true&downloadRank=true)](https://www.npmjs.com/package/p3x-binary-search-closest/) [![Donate for Corifeus / P3X](https://img.shields.io/badge/Donate-Corifeus-003087.svg)](https://paypal.me/patrikx3) [![Contact Corifeus / P3X](https://img.shields.io/badge/Contact-P3X-ff9900.svg)](https://www.patrikx3.com/en/front/contact) [![Corifeus @ Facebook](https://img.shields.io/badge/Facebook-Corifeus-3b5998.svg)](https://www.facebook.com/corifeus.software) [![Uptime Robot ratio (30 days)](https://img.shields.io/uptimerobot/ratio/m780749701-41bcade28c1ea8154eda7cca.svg)](https://stats.uptimerobot.com/9ggnzcWrw) # 🚅 Find the closest or exact value using binary search v2024.4.104 **Bugs are evident™ - MATRIX️** ### NodeJS LTS is supported ### Built on NodeJs version ```txt v20.11.0 ``` # Description [//]: #@corifeus-header:end Before, you want to find the closest or exact value in an [array of objects](https://www.scaler.com/topics/javascript-sort-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 ```bash npm install p3x-binary-search-closest ``` # Usage If 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, than when we are in the event loop, so the worker thread is valid when we are working on a big dataset. ```js 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) }) }) ``` [//]: #@corifeus-footer --- 🙏 This is an open-source project. Star this repository, if you like it, or even donate to maintain the servers and the development. Thank you so much! Possible, this server, rarely, is down, please, hang on for 15-30 minutes and the server will be back up. All my domains ([patrikx3.com](https://patrikx3.com) and [corifeus.com](https://corifeus.com)) could have minor errors, since I am developing in my free time. However, it is usually stable. **Note about versioning:** Versions are cut in Major.Minor.Patch schema. Major is always the current year. Minor is either 4 (January - June) or 10 (July - December). Patch is incremental by every build. If there is a breaking change, it should be noted in the readme. --- [**P3X-BINARY-SEARCH-CLOSEST**](https://corifeus.com/binary-search-closest) Build v2024.4.104 [![Donate for Corifeus / P3X](https://img.shields.io/badge/Donate-Corifeus-003087.svg)](https://www.paypal.com/cgi-bin/webscr?cmd=_s-xclick&hosted_button_id=QZVM4V6HVZJW6) [![Contact Corifeus / P3X](https://img.shields.io/badge/Contact-P3X-ff9900.svg)](https://www.patrikx3.com/en/front/contact) [![Like Corifeus @ Facebook](https://img.shields.io/badge/LIKE-Corifeus-3b5998.svg)](https://www.facebook.com/corifeus.software) [//]: #@corifeus-footer:end browser.js000066400000000000000000000002151516076774300131150ustar00rootroot00000000000000const util = require('./src/util') module.exports = { byProperty: util.binarySearchByProperty, byValue: util.binarySearchByValue, } package.json000066400000000000000000000022561516076774300133710ustar00rootroot00000000000000{ "name": "p3x-binary-search-closest", "version": "2024.4.104", "corifeus": { "icon": "fas fa-train", "prefix": "p3x-", "publish": true, "type": "p3x", "code": "Bullet", "nodejs": "v20.11.0", "opencollective": false, "reponame": "binary-search-closest", "build": true }, "description": "🚅 Find the closest or exact value using binary search", "main": "src/index.js", "scripts": { "test": "grunt && mocha ./test/mocha/*.js" }, "repository": { "type": "git", "url": "git+https://github.com/patrikx3/binary-search-closest.git" }, "keywords": [ "search", "binary-search", "binary", "value", "object", "property", "closest", "exact" ], "author": "Patrik Laszlo ", "license": "MIT", "bugs": { "url": "https://github.com/patrikx3/binary-search-closest/issues" }, "homepage": "https://corifeus.com/binary-search-closest", "devDependencies": { "corifeus-builder": "^2024.4.103" }, "engines": { "node": ">=12.13.0" } }src/000077500000000000000000000000001516076774300116655ustar00rootroot00000000000000src/index.js000066400000000000000000000003241516076774300133310ustar00rootroot00000000000000const util = require('./util') const utilWorker = require('./util.worker') module.exports = { byProperty: util.binarySearchByProperty, byValue: util.binarySearchByValue, worker: utilWorker.worker, } src/util.js000066400000000000000000000056121516076774300132040ustar00rootroot00000000000000 const binarySearchByProperty = (obj, target, property) => { const n = obj.length // Corner cases if (target <= obj[0][property]) { return obj[0]; } if (target >= obj[n - 1][property]) { return obj[n - 1]; } // Doing binary search let i = 0, j = n, mid = 0; while (i < j) { mid = Math.floor((i + j) / 2) if (obj[mid][property] == target) { return obj[mid]; } /* If target is less than array element, then search in left */ if (target < obj[mid][property]) { // If target is greater than previous // to mid, return closest of two if (mid > 0 && target > obj[mid - 1][property]) { return binarySearchByPropertyGetClosest(obj[mid - 1], obj[mid], target, property); } /* Repeat for left half */ j = mid; } else { // If target is greater than mid if (mid < n - 1 && target < obj[mid + 1][property]) { return binarySearchByPropertyGetClosest(obj[mid], obj[mid + 1], target, property); } // update i i = mid + 1; } } // Only single element left after search return obj[mid]; } const binarySearchByPropertyGetClosest = (val1, val2, target, property) => { if (target - val1[property] >= val2[property] - target) { return val2; } else { return val1; } } const binarySearchByValue = (obj, target) => { const n = obj.length // Corner cases if (target <= obj[0]) { return obj[0]; } if (target >= obj[n - 1]) { return obj[n - 1]; } // Doing binary search let i = 0, j = n, mid = 0; while (i < j) { mid = Math.floor((i + j) / 2) if (obj[mid] == target) { return obj[mid]; } /* If target is less than array element, then search in left */ if (target < obj[mid]) { // If target is greater than previous // to mid, return closest of two if (mid > 0 && target > obj[mid - 1]) { return binarySearchByValueGetClosest(obj[mid - 1], obj[mid], target); } /* Repeat for left half */ j = mid; } else { // If target is greater than mid if (mid < n - 1 && target < obj[mid + 1]) { return binarySearchByValueGetClosest(obj[mid], obj[mid + 1], target); } // update i i = mid + 1; } } // Only single element left after search return obj[mid]; } const binarySearchByValueGetClosest = (val1, val2, target) => { if (target - val1 >= val2 - target) { return val2; } else { return val1; } } module.exports.binarySearchByProperty = binarySearchByProperty module.exports.binarySearchByValue = binarySearchByValue src/util.worker.js000066400000000000000000000011311516076774300145040ustar00rootroot00000000000000const worker = async (options) => { const { Worker } = require('worker_threads'); const workerResult = await new Promise((resolve, reject) => { const worker = new Worker(`${__dirname}/worker.js`, { workerData: options }); worker.on('message', resolve); worker.on('error', reject); worker.on('exit', (code) => { if (code !== 0) { reject(new Error(`Worker stopped with exit code ${code}`)); } worker.terminate() }); }); return workerResult }; module.exports.worker = worker src/worker.js000066400000000000000000000016211516076774300135340ustar00rootroot00000000000000const { parentPort, workerData } = require('worker_threads'); const util = require('./util'); const allowedTypes = ['value', 'property'] let type = workerData.type const array = workerData.array const target = workerData.target const property = workerData.property if (type === undefined) { type = allowedTypes[0] } if (!allowedTypes.includes(type)) { throw new Error(`The allowed types are ${allowedTypes.join(', ')}, you tried ${type}`) } if (type === 'property' && (typeof property !== 'string' || property.length < 1)) { throw new Error(`You tried by searching by binarySearchByProperty, but you forgot the property options, which has to be a string and at least one character`) } let foundValue if (type === 'value') { foundValue = util.binarySearchByValue(array, target) } else { foundValue = util.binarySearchByProperty(array, target, property) } parentPort.postMessage(foundValue) test/000077500000000000000000000000001516076774300120555ustar00rootroot00000000000000test/mocha/000077500000000000000000000000001516076774300131445ustar00rootroot00000000000000test/mocha/test.js000066400000000000000000000132401516076774300144610ustar00rootroot00000000000000const assert = require('assert'); const bsClosest = require('../../src') 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) }) })