Problem: Find the position to insert an element into a sorted array
A[1] > A[2] > A[3] > ... > A[ n ]
- Show the best and worst case.
- 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