Finding an optimal solution to the "Where Do I Belong" challenge

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);
``````
2 Likes
``````      ***** Where do I belong (My Solution) *****
``````

function getIndexToIns(arr, num) {

arr.push(num);

function sort(a,b){

return a - b ;

}

return arr.sort(sort).indexOf(num);

}

1 Like