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

Finding an optimal solution to the "Where Do I Belong" challenge
0.0 0
#1

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;
}
#2

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;
#3

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.

#4

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);