This algorithm is actually called Where do I belong?
.
Challenge:
1 |
Return the lowest index at which a value (second argument) should be inserted into an array (first argument) once it has been sorted. |
For example:
1 2 3 |
getIndexToIns([1,2,3,4], 1.5) should return 1 because it is greater than 1 (index 0), but less than 2 (index 1). Likewise, getIndexToIns([20,3,5], 19)should return 2 because once the array has been sorted it will look like [3,5,20] and19 is less than 20 (index 2) and greater than5 (index 1). |
Some helpful links:
You know your code has passed when:
1 2 3 4 5 6 7 |
getIndexToIns([10, 20, 30, 40, 50], 35) should return3. getIndexToIns([10, 20, 30, 40, 50], 30) should return2. getIndexToIns([40, 60], 50) should return 1. getIndexToIns([3, 10, 5], 3) should return 0. getIndexToIns([5, 3, 20, 3], 5) should return 2. getIndexToIns([2, 20, 10], 19) should return 2. getIndexToIns([2, 5, 10], 15) should return 3. |
What I was given to work with as a start:
1 2 3 4 5 6 7 8 |
function getIndexToIns(arr, num) { // Find my place in this sorted array. return num; } getIndexToIns([ 40, 60 ], 50); |
My pseudo code for the challenge:
1 2 3 |
push the argument object num into the argument array (arr). Sort the new array. Return the index of the pushed number after the array has been sorted. |
arr.sort(): sorts the elements of an array in place and returns the array. The sort is not necessarily stable. The default sort order is according to Unicode code points.
arr.sort() parameters:
compareFunction: Optional. Specifies a function that defines the sort order. If omitted, the array is sorted according to each character’s Unicode code point value, according to the string conversion of each element.
compareFunction description (if compareFunction is not supplied): elements are sorted by converting them to strings and comparing strings in Unicode code point order. For example, “banana” comes before “cherry”. In a numeric sort, 9 comes before 80, but because numbers are converted to strings, “80” comes before “9” in Unicode order.
compareFunction description (if compareFunction is supplied): array elements are sorted according to the return value of the compare function. If a and b are two elements being compared, then:
- if compareFunction(a, b) is < 0, sort a to a lower index than b, i.e., a comes first.
- if compareFunction(a, b) === 0, leave a & b unchanged with respect to each other, but sorted with respect to all different elements. Note: the ECMAscript standard does not guarantee this behaviour, and thus not all browsers (e.g. Mozilla versions dating back to at least 2003) respect this.
- if compareFunction(a,b) > 0, sort be to a lower index than a.
- compareFunction(a, b) must always return the same value when given a specific pair of elements a and b as its two arguments. If inconsistent results are returned then the sort order is undefined.
Articulation of my solution:
- I knew that I had to push the second (provided) argument (num) into the first argument (arr) before I could do anything else. This is represented by arr.push(num);
- Then I knew that I had to sort this “new” array. This is represented by arr.sort(compareFunction), which is in turn represented by arr.sort(function(a, b) { return a-b }.
- Lastly, I had to “return the index of the pushed number after the array has been sorted”. This is represented by return arr.indexOf(num). To learn more about how .indexOf() works, please visit my earlier post Why Array.prototype.slice.call() is helpful when working with both arrays and objects.
My solution to the challenge:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
function getIndexToIns(arr, num) { // Find my place in this sorted array. arr.push(num); arr.sort(function(a, b) { return a - b; }); return arr.indexOf(num); } getIndexToIns([ 40, 60 ], 50); |
1 2 3 4 5 6 7 8 9 10 11 |
function getIndexToIns(arr, num) { // Find my place in this sorted array. arr.push(num); arr.sort((a, b) => a - b); return arr.indexOf(num); } getIndexToIns([ 40, 60 ], 50); |
This was first published here on May 5, 2016 @ 14:55. It was part of freecodecamp.org’s Basic JavaScript Algorithm Scripting for the Front End Development certification.
Comment Policy: Your words are your own, so be nice and helpful if you can. Please, only use your real name and limit the amount of links submitted in your comment. We accept clean XHTML in comments, but don't overdo it please. Comments are moderated, so spammy or malicious links will be removed.