Created
December 19, 2022 17:35
-
-
Save 1solation/e24d441c55051f0778810a6f767afb4c to your computer and use it in GitHub Desktop.
coding problem - binary search function in JS, with comments
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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