2
$\begingroup$

Suppose we are given A, an array of size n, comprised of an increasing sequence of numbers followed immediately by a decreasing one. What is worst case time complexity of optimal algorithm to determine if a given number x is in the array?

The explanation given on the this site is confusing to me. How we can apply binary search on unsorted array?

They have provided following explanation => This is an application of Binary search, which has time complexity $Θ(log n)$ in worst case.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
3
$\begingroup$

We can find the break point (where the type of sequence changes) in theta(log n). Then we can search individually on both sides of the break point (each of which is a sorted sequence). So overall theta(log n) only.

Improve this answer
$\endgroup$
2
$\begingroup$

First use binary search to find the index, where the ordering changes from increasing to decreasing. Now you can use binary search on both partitions of the array.

Improve this answer
$\endgroup$
1
  • $\begingroup$ You mean to say break point increasing to decreasing. $\endgroup$
    – user82290
    Jan 11, 2018 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.