Skip to content

Instantly share code, notes, and snippets.

@1solation
Created December 19, 2022 17:35
Show Gist options
  • Save 1solation/e24d441c55051f0778810a6f767afb4c to your computer and use it in GitHub Desktop.
Save 1solation/e24d441c55051f0778810a6f767afb4c to your computer and use it in GitHub Desktop.
coding problem - binary search function in JS, with comments
function binary_search(x, sorted_collection, low = 0, high = null) {
// x is target
// sorted_collection I will assume is always sorted in ascending numerical order AND starting from 1
// low is the start index
// high is the end index
if (high === null) {
high = sorted_collection.length; // using .length will return 1 index higher as arrays start with a 0 index, not 1
} else if (high < 0) {
throw new RangeError("High index out of range");
}
if (low > high) return null;
const mid = Math.floor((high + low) / 2);
const value = sorted_collection[mid];
if (value == x) {
// loose equality check here, checks whether its two operands are equal e.g. '1' == 1 will output true. See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Equality
// rather than strict equality which will try to convert and then compare the operands e.g. '1' === 1 will output false. See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Strict_equality
return value; // value is the actual value at sorted_collection[mid], not the index itself
} else if (value > x) {
// if middle value is greater than target value of x, we should search left using middle as ending index
return binary_search(x, sorted_collection, mid + 1, high);
} else {
// if target value is not inside the sorted_collection, we will trigger the conditional on line 8 & then throw the error on line 9
return binary_search(x, sorted_collection, low, mid - 1);
}
}
// Don't change anything below this line ;)
const tests = [
{
find: 1,
collection: [],
expected: null,
},
{
find: 1,
collection: [1],
expected: 0,
},
{
find: 2,
collection: [1],
expected: null,
},
{
find: 1,
collection: [1, 2],
expected: 0,
},
{
find: 2,
collection: [1, 2],
expected: 1,
},
{
find: 3,
collection: [1, 2, 3],
expected: 2,
},
{
find: 1,
collection: [1, 2, 3, 4],
expected: 0,
},
{
find: 2,
collection: [1, 2, 3, 4],
expected: 1,
},
{
find: 3,
collection: [1, 2, 3, 4],
expected: 2,
},
{
find: 4,
collection: [1, 2, 3, 4],
expected: 3,
},
{
find: 1,
collection: [1, 2, 3, 4, 5],
expected: 0,
},
{
find: 2,
collection: [1, 2, 3, 4, 5],
expected: 1,
},
{
find: 3,
collection: [1, 2, 3, 4, 5],
expected: 2,
},
{
find: 4,
collection: [1, 2, 3, 4, 5],
expected: 3,
},
{
find: 5,
collection: [1, 2, 3, 4, 5],
expected: 4,
},
{
find: 99,
collection: [1, 2, 3, 4, 5],
expected: null,
},
];
const results = tests.map(function (test) {
try {
var result = binary_search(test["find"], test["collection"]);
test.result = result;
test.success = result == test["expected"];
} catch (ex) {
test.result = ex.message;
test.success = false;
}
return test;
});
console.table(results);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment