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.
-
$\begingroup$ Yes, you can! Look here for an exposition: mathmeth.com/wf/files/wf2xx/wf214t.ps or, more accessibly, here iis.sinica.edu.tw/~scm/ncs/2010/03/binary-search-revisited No sorting required! $\endgroup$Musa Al-hassy– Musa Al-hassy2018年01月15日 14:08:23 +00:00Commented Jan 15, 2018 at 14:08
2 Answers 2
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.
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.
-
$\begingroup$ You mean to say break point increasing to decreasing. $\endgroup$user82290– user822902018年01月11日 23:08:04 +00:00Commented Jan 11, 2018 at 23:08