Geek Answers Handbook

Find the smallest element in an array that has a pattern

The array is set in such a way that its element value increases from the 0th index to some (k-1) index. In k, the value is minimal, and it again begins to increase through the element n . Find the minimal element.

Essentially, its one sorted list is added to another; Example: (1, 2, 3, 4, 0 , 1, 2, 3).

I tried all kinds of algorithms like scary mini-heap, quick pick or simple intersection. But I can not get it below O (n). But there is a template in this array, what binary search implies should be possible, and complexity should be something like O (log n), but cannot find anything. Thoughts ??

thank

+5
source share
4 answers

No. A drop can be anywhere, there is no structure for this.

Let's consider extrema

1234567890
9012345678
1234056789
1357024689

It comes down to finding the minimum element.

+4
source

Do a binary width search to reduce the range, with a singleton overlap in binary partitions. In other words, if you had, say, 17 elements, compare the elements

0,8
8,16
0,4
4,8
8,12
12,16
0,2
2,4

etc., looking for a case where the left element is larger than the right.

Once you find such a range, repeat the procedure by doing the same binary search in that range. Repeat until you find a diminishing adjacent pair.

O (log n), O (n). - ? " " O (log n) O (n), , . .

1, O (log n).

+1

, O (n).

-

a1, a2, a3.... ak, ak + 1... an

ak < ak-1, . 1,2,3,4,5,6,4,7,8,9,10

'k' 'ak'

+1

The simplest solution is to simply scroll through the list until the next value is less than the current, or backward to find a value that is larger than the current. This is O (n).

The execution of both will be O (n) at the same time, but the execution time is likely to be faster (depending on complex processor / cache factors).

I don’t think you can do it much faster algorithmically than O (n), as many search and delimited search algorithms rely on a sorted dataset.

0
source

More articles:


All Articles