Array Floor

Computer Science Level 1

Given an array and an element $x$ , the floor of an element $x$ is defined as the greatest element present in the array which is less than or equal to $x$ .

What is the worst case complexity of the most efficient algorithm for finding a floor of an element $x$ in a sorted array?

Details and Assumptions :

If the array is $[3, 8, 15, 19, 23]$ and $x=20$ , then the output will be $19$ .
$x$ can't be less than the minimum element in the list.

O(n\log n)

O(\log n)

O(n)

O(\log\log(n))

1 solution

Patent Fox
Mar 6, 2018

Finding floor of an integer is O(1) operation .

Finding a particular integer x in a sorted array is O(log n) operation using binary search .

Combining these 2, worst case complexity of Array Floor algorithm is O(log n)

it was never said the array is sorted. adding such assumption is wrong.

datsounds plausible - 3 years, 1 month ago

It is in fact explicitly mentioned
"What is the worst case complexity of the most efficient algorithm for finding a floor of an element $x$ in a sorted array?"

patent fox - 3 years, 1 month ago

Its explicitly written

patent fox - 1 year, 7 months ago

I think you're right for the wrong reasons Kaustubh, because it doesn't ask us to find the floor of an integer, it asks us to find the greatest number less than some value n in the array. So you just find n with binary search and then look left one index. So it's still O(log n) but there's no 'floor' operation.

Eric Glover - 1 year, 5 months ago

@Eric Glover Yes, you are right, I didn't read the statement thoroughly. But yes, as you mentioned, finding floor as described in problem statement is also a O(log(n)) problem

patent fox - 3 months, 4 weeks ago

Array Floor

1 solution

0 pending reports