1
$\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.

$\endgroup$
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.

$\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.

$\endgroup$
  • $\begingroup$ You mean to say break point increasing to decreasing. $\endgroup$ – user82290 Jan 11 '18 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy