.editorconfig 0000664 0000000 0000000 00000000637 15166455067 0013560 0 ustar 00root root 0000000 0000000 # EditorConfig helps developers define and maintain consistent
# coding styles between different editors and IDEs
# editorconfig.org
root = true
[*]
# Change these settings to your own preference
indent_style = space
indent_size = 4
# We recommend you to keep these unchanged
end_of_line = lf
charset = utf-8
trim_trailing_whitespace = true
insert_final_newline = true
[*.md]
trim_trailing_whitespace = false
.gitignore 0000664 0000000 0000000 00000000335 15166455067 0013066 0 ustar 00root root 0000000 0000000 /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
.idea/ 0000775 0000000 0000000 00000000000 15166455067 0012055 5 ustar 00root root 0000000 0000000 .idea/$CACHE_FILE$ 0000664 0000000 0000000 00000000237 15166455067 0013514 0 ustar 00root root 0000000 0000000
.idea/.gitignore 0000664 0000000 0000000 00000000260 15166455067 0014043 0 ustar 00root root 0000000 0000000 # Default ignored files
/shelf/
/workspace.xml
# Datasource local storage ignored files
/dataSources/
/dataSources.local.xml
# Editor-based HTTP Client requests
/httpRequests/
.idea/binary-search-closest.iml 0000664 0000000 0000000 00000000520 15166455067 0016756 0 ustar 00root root 0000000 0000000
.idea/misc.xml 0000664 0000000 0000000 00000000423 15166455067 0013531 0 ustar 00root root 0000000 0000000
.idea/modules.xml 0000664 0000000 0000000 00000000446 15166455067 0014253 0 ustar 00root root 0000000 0000000
.npmignore 0000664 0000000 0000000 00000000250 15166455067 0013071 0 ustar 00root root 0000000 0000000 /.idea
/artifacts
/build
/Gemfile
/_layouts
/_site
/_includes
/test
/node_modules
/*.iml
/*.ipr
/*.iws
/.travis.yml
/.scrutinizer.yml
/Gruntfile.js
/corifeus-boot.json
.travis.yml 0000664 0000000 0000000 00000001455 15166455067 0013213 0 ustar 00root root 0000000 0000000 language: node_js
cache:
npm: false
node_js:
- lts/*
before_script:
- npm install -g grunt-cli npm
env:
global:
secure: KZ0VSEvR4z9sxJU8RNdWc/1E8yotxrWYOVXkcH7cBtbodW5fRlva5K9DZKJzUf55umzF/zCzudWU740EAkUm4ciFYzEWPbpU4eHLJGInu4fo8zmfyKcJY6AJE4XpjPEs7pJfZyHik2R0ycWggV+Hn0lwXRhobicXRPCsDhLfnFkHIyzCGYQEMzmOzYB0MXvVxlvgxdyZvSbX6tfh6WRBe7KQLEBE6GzBYsXLDyRujyxHtcMOwqT4YVTNI/KEJXxdR7OBxvNKnyLZ68h6uWIPPnV6hfoBKnxKiAbZC+epL0zmpvMMOZoW49+mV1o/OX3sCbmHvGmH6sefV4sslBHEVlh+ARZfFZHfL60XIzbwHzzlfviKwnzrwBjaUTJiTXfl8xm/Z1TwujsIfDeObj1u26vq2aG2UDAqzjSlr8O3NPRV2ApNgK4C4wXrPLtAp8HAkG6U7fG5qdnLFgQCcbj07VMxSZVCcM4ULpeqGnlL1vBS25Qe/Ntpt7DGC/6PA2ucLU9V4FszaNgn2fQ9fyKa6z1v8fOuq2Lpes4lUx1LYR06Vu4yca3yEIEsT7jry3MfKNiuFP/KbgTgV8cU+dLbIrJRlu6D5vslzNSExGAHXCCZv6BfJXXa/nyff6NhczpD2hhNZRdojWX01AGKWNi+5K+mPoU78O58N/gZ+4cpv2Q=
Gruntfile.js 0000664 0000000 0000000 00000000526 15166455067 0013375 0 ustar 00root root 0000000 0000000 const 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);
}
LICENSE 0000664 0000000 0000000 00000002345 15166455067 0012106 0 ustar 00root root 0000000 0000000
@license p3x-binary-search-closest v2020.4.127
🚅 Find the closest value using binary search
https://corifeus.com/binary-search-closest
Copyright (c) 2020 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.md 0000664 0000000 0000000 00000005412 15166455067 0012356 0 ustar 00root root 0000000 0000000 [//]: #@corifeus-header
[](https://www.npmjs.com/package/p3x-binary-search-closest/)
[](https://paypal.me/patrikx3) [](https://www.patrikx3.com/en/front/contact) [](https://www.facebook.com/corifeus.software) [](https://travis-ci.com/patrikx3/binary-search-closest)
[](https://uptimerobot.patrikx3.com/)
# 🚅 Find the closest value using binary search v2020.4.127
**Bugs are evident™ - MATRIX️**
### NodeJs LTS Version Requirement
```txt
>=12.13.0
```
### Built on NodeJs
```txt
v12.16.3
```
The ```async``` and ```await``` keywords are required. Only the latest LTS variant is supported.
Install NodeJs:
https://nodejs.org/en/download/package-manager/
# Description
[//]: #@corifeus-header:end
[//]: #@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 v2020.4.127
[](https://www.paypal.com/cgi-bin/webscr?cmd=_s-xclick&hosted_button_id=QZVM4V6HVZJW6) [](https://www.patrikx3.com/en/front/contact) [](https://www.facebook.com/corifeus.software)
## P3X Sponsor
[IntelliJ - The most intelligent Java IDE](https://www.jetbrains.com/?from=patrikx3)
[](https://www.jetbrains.com/?from=patrikx3)
[//]: #@corifeus-footer:end
binary-search-closest.iml 0000664 0000000 0000000 00000000517 15166455067 0016004 0 ustar 00root root 0000000 0000000
package.json 0000664 0000000 0000000 00000002034 15166455067 0013362 0 ustar 00root root 0000000 0000000 {
"name": "p3x-binary-search-closest",
"version": "2020.4.127",
"corifeus": {
"icon": "fas fa-train",
"prefix": "p3x-",
"publish": true,
"type": "p3x",
"code": "Bullet",
"nodejs": "v12.16.3",
"opencollective": false,
"reponame": "binary-search-closest",
"build": true
},
"description": "🚅 Find the closest 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"
],
"author": "Patrik Laszlo ",
"license": "MIT",
"bugs": {
"url": "https://github.com/patrikx3/binary-search-closest/issues"
},
"homepage": "https://corifeus.com/binary-search-closest",
"dependencies": {
"corifeus-builder": "^2020.4.205"
},
"engines": {
"node": ">=12.13.0"
}
} src/ 0000775 0000000 0000000 00000000000 15166455067 0011664 5 ustar 00root root 0000000 0000000 src/index.js 0000664 0000000 0000000 00000000350 15166455067 0013327 0 ustar 00root root 0000000 0000000 const { Worker } = require('worker_threads');
const util = require('./util')
module.exports = {
binarySearchByProperty: util.binarySearchByProperty,
binarySearchByValue: util.binarySearchByValue,
worker: util.worker,
}
src/util.js 0000664 0000000 0000000 00000006740 15166455067 0013206 0 ustar 00root root 0000000 0000000
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;
}
}
const 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.binarySearchByProperty = binarySearchByProperty
module.exports.binarySearchByValue = binarySearchByValue
module.exports.worker = worker
src/worker.js 0000664 0000000 0000000 00000001621 15166455067 0013533 0 ustar 00root root 0000000 0000000 const { 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/ 0000775 0000000 0000000 00000000000 15166455067 0012054 5 ustar 00root root 0000000 0000000 test/mocha/ 0000775 0000000 0000000 00000000000 15166455067 0013143 5 ustar 00root root 0000000 0000000 test/mocha/test.js 0000664 0000000 0000000 00000013273 15166455067 0014466 0 ustar 00root root 0000000 0000000 const 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.binarySearchByValue(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.binarySearchByValue(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.binarySearchByProperty(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.binarySearchByProperty(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('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)
})
})