Find the position to insert an element into a sorted array
NickName:Andre Araujo Ask DateTime:2017-04-19T06:40:26

Find the position to insert an element into a sorted array

Problem: Find the position to insert an element into a sorted array

A[1] > A[2] > A[3] > ... > A[ n ]
  1. Show the best and worst case.
  2. Write an algorithm to solve the problem

My answer:

The best case is T(n) = 1 in other words in a first position where n is the size of elements. The worst case will be T(n) = n + 1 in other words the last position + 1.

  def find_position(element, l):
        i = 0
        inserted = False
        for item in l:
            if element < item:
                inserted =  True
                break
            i = i +1
        if not inserted:
            return len(l)
        else:
            return i

Some other students had written a binary search that the worst case is better than mine and told me that my answer is incorrect. But I disagree because the exercise was not explicit to write an optimized algorithm.

Is there any mistake in my logic?

Copyright Notice:Content Author:「Andre Araujo」,Reproduced under the CC 4.0 BY-SA copyright license with a link to the original source and this disclaimer.
Link to original article:https://stackoverflow.com/questions/43483367/find-the-position-to-insert-an-element-into-a-sorted-array

Answers
hulud 2017-04-18T22:44:37

Given what you said where the conditions are simply:\n\n1)write an algorithm to solve a problem\n2)analyze the asymptotic complexity of said problem\n\nYou clearly did those. Your solution is just the obvious one, not the best one. ",


SuperNova 2017-04-20T06:52:36

Just check if it falls in after the number(something like below..)\n\nfor l in range(0, len(lst)):\n if lst[l] >= number_to_be_inserted:\n lst.insert(l+1, number_to_be_inserted)\n break\n",


More about “Find the position to insert an element into a sorted array” related questions

Find the position to insert an element into a sorted array

Problem: Find the position to insert an element into a sorted array A[1] &gt; A[2] &gt; A[3] &gt; ... &gt; A[ n ] Show the best and worst case. Write an algorithm to solve the problem My answer...

Show Detail

How to find correct position to insert an element in a sorted array?

I have to make a program in Java to create a sorted array in descending order. When i try to insert 10, 3 it is ok, but when i insert 10, 3, 8 the result is 10, 8, 0. For some reason the 0 appears ...

Show Detail

How to insert an element in a sorted array so the the array remains sorted?

In c++, std::set which stores its element in sorted order can insert elements in O(log n) time. But all the methods i know take linear time: Inserting the element at the end of the array and swapp...

Show Detail

Find First and Last Position of Element in Sorted Array

I am trying to solve the LeetCode problem Find First and Last Position of Element in Sorted Array: Given an array of integers nums sorted in ascending order, find the starting and ending position ...

Show Detail

Return the insert position of an element into a sorted array with Binary Search Recursion

I want to return the position of an element from a sorted array if that element exist otherwise I want to return the insert position where the element should be inserted. Here is my code: public

Show Detail

Insert an element into a sorted array

I wrote this function to insert an element into a sorted array such that array would still be sorted after adding the element. But something is wrong. I know that my code has a lot of edge cases ...

Show Detail

How do I insert an element at the correct position into a sorted array in Swift?

NSArray has - (NSUInteger)indexOfObject:(id)obj inSortedRange:(NSRange)r options:(NSBinarySearchingOptions)opts usingComparator:(NSComparator)cmp to determine the insert position of a new object in a

Show Detail

How do I insert an element at the correct position into a sorted array in Swift?

NSArray has - (NSUInteger)indexOfObject:(id)obj inSortedRange:(NSRange)r options:(NSBinarySearchingOptions)opts usingComparator:(NSComparator)cmp to determine the insert position of a new object in a

Show Detail

How do I insert an element at the correct position into a sorted array in Swift?

NSArray has - (NSUInteger)indexOfObject:(id)obj inSortedRange:(NSRange)r options:(NSBinarySearchingOptions)opts usingComparator:(NSComparator)cmp to determine the insert position of a new object in a

Show Detail

Insert an element to Array List sorted descending order

I'm trying to insert an element in the correct position in an array list that is sorted in descending order. The complexity to find the correct position must be O(LOGN). That's why I tried using bi...

Show Detail