Algorithm for finding the first bigger integer with o-small(n) complexity

Question

I need to write an algorithm, which will find the first integer, which is bigger than x in a sorted array, where integers may repeat. The algorithm should have the complexity of o(n), where o is small. What is the difference between the algorithms with O(n) an o(n) difficulty?

o(n) means that lim f(n) /n=0, so you can have sqrt(n) algorithm or log(n) they both are o(n) — kingW3, Oct 20 '18 at 14:06

score 2 · Answer 1 · answered Oct 20 '18 at 14:14

2

You can using binary search method to find the first biggest integer of x. It would in O(log(n)) = small_o(n).

answered Oct 20 '18 at 14:14

OmG

18,337
10
57
90

score 1 · Answer 2 · answered Oct 20 '18 at 14:22

1

Here is a very good and in depth explanation of big-o vs little-o notation: Difference between Big-O and Little-O Notation

The most simple yet efficient algorithm is Binary Search as @OmG mentioned, and here is the link to start: https://en.wikipedia.org/wiki/Binary_search_algorithm

The idea is pretty simple: you just compare the number you search with the middle element of the array, if the middle is less then your number it's obvious that you need to find on the right half, ... otherwise left half. You stop when there is only one element.

answered Oct 20 '18 at 14:22

Keloo

1,368
1
17
36

The binary search algorithm is for searching the exact number, as far as I understand. Do I understand right, that after finding the exact x element in the array, I need to check every next element in this array (iterate) to find the next bigger one? Wouldn't the whole complexity be worse than log(n) in this case? – George P. Oct 20 '18 at 14:51
you do not find the exact element, you find the first bigger element than your target. – Keloo Oct 21 '18 at 13:45
the next element is obviously the next bigger, the next next is 3rd bigger and so on. – Keloo Oct 21 '18 at 13:45
I think not necessarily, if the elements may repeat, or miss. – George P. Oct 21 '18 at 15:12
well yes if the elements repeat then yes. – Keloo Oct 21 '18 at 15:35

score 1 · Answer 3 · answered Oct 20 '18 at 14:42

As people have pointed out before me, you want to do a binary search. This post includes example code:

In python this is easiest with the bisect function: https://docs.python.org/2/library/bisect.html

from bisect import bisect_right

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

Algorithm for finding the first bigger integer with o-small(n) complexity

3 Answers3