A js solution with binary search --O(lgn)


  • 0
    L

    /**

    • @param {number[]} A

    • @param {number} target

    • @return {number}
      */
      var searchInsert = function(A, target) {
      var start=0;
      var end = A.length-1;

      if(target <= A[0])
      {
      return 0;
      }

      if(target > A[end])
      {
      return A.length;
      }
      if(target === A[end])
      {
      return end;
      }

    var middle = 0;
    while(start <= end)
    {
        middle = Math.floor((start + end)/2);
        if(target < A[middle])
        {
            end = middle-1;
        }
        else if(target > A[middle])
        {
            start = middle + 1;
        }
        else
        {
            return middle;
        }
    }
    
    if(end === middle)
    {
        return middle + 1;
        
    }
    if(start === middle)
    {
        return middle;
        
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.