Hi everyone, hope you’re all having fun. I hit the “Where Do I Belong” challenge last night and though my first solution was very simple, I kept wondering what would happen if the list were 1000 elements long and the actual place for insertion happened to be at the end of the list. I tried something else instead, which involved pruning away half the list and then iterating through the remainder. From my (dated) knowledge I recall that as being a binary tree search, but I’m not clear on the implementation in Javascript.
Can anyone review my code below and provide some guidance on how I could implement same towards solving this problem? Would greatly appreciate it!
function getIndexToIns(arr, num) {
// Find my place in this sorted array.
arr.sort(function(a,b){
return a-b;
});
var i;
//Partition the array into items greater than/equal to or less than than num and iterate through the remainder...
var searchIdx = Math.ceil(arr.length/2) - 1;
if(arr[searchIdx] == num){
return searchIdx;
} else if(arr[searchIdx] > num){
for(i = searchIdx; i >=0; i--){
if(arr[i] <= num){
return i;
}
}
} else if(arr[searchIdx] < num){
for(i = searchIdx; i < arr.length; i++){
if(arr[i] >= num){
return i;
}
}
}
return i;
}
This approach works but if they array is large you will still end up checking a lot of vars. I would suggest continuing to check the half-way points until you have one that’s less followed by one that higher or you only have one left. However it’s possible to use some built-in array functions to solve this a lot quicker.
function getIndexToIns(arr, num) {
//1. Check if number is already in the array
if (arr.indexOf (num)!==-1){ return arr.indexOf (num); }
//2. Find the next highest number and it's index
var target_index=0;
arr.reduce (function (t,cv,ind){ if (cv > t && cv < num){ t=cv; target_index=ind; } return t; });
//3. Use that value
return target_index;
Thanks a lot! For some reason I thought that indexOf() could only be used for strings…this is a whole lot faster. Not familiar with the reduce function but going to do some reading and will be rewriting this one.
I also used the indexOf function, but I did not reduce.
function getIndexToIns(arr, num) {
// Find my place in this sorted array.
// game plan
// 1. push num to array
// 2. sort array (careful here, need to convert as numbers and not strings)
// 3. find num's index in the array
// 4. index is the answer num
arr.push(num);
arr.sort(function(a, b) {return a - b;} );
return arr.indexOf(num);
}
// getIndexToIns([3, 10, 5], 3);
getIndexToIns([2, 20, 10], 19);