I'm having a hard time solving this problem.

```
A[1..n] is an array of real numbers which is partially sorted:
There are some p,q (1 <= p <= q <=n) so:
A[1] <= ... <= A[p]
A[p] >= ... >= A[q]
A[q] <= ... <= A[n]
How can we find a value in this array in O(lgn)?
(You can assume that the value exists in the array)
```

Make 3 binary searches: from 1 to p, p to q and q to n. The complexity is still O(logn).

**Since we don't know p and q:**

You cannot solve this problem in logn time. Assume a case where you have a sorted list of positive numbers with one zero mixed in (p+1=q and A[q]=0). This situation satisfies all the criteria you mentioned. Now, the problem of finding where that zero is located cannot be solved in sub O(n) time. Therefore your problem cannot be solved in O(logn) time.

Despite the "buried zero" worst case already pointed out, I would still recommend implementing an algorithm that can often speed things up, depending on p,q. For example, suppose that you have n numbers, and each increasing and decreasing region has size at least k. Then if you check 2^m elements in your array, including the first and last element and the rest of the elements as equally spaced as possible, starting with m=2 and then iteratively increasing m by 1, eventually you will reach m when you find 3 pairs of consecutive elements (A,B),(C,D),(E,F) from left-to-right out of the 2^m elements that you have checked, which satisfy A < B, C > D, E < F (some pairs may share elements). If my back-of-the-envelope calculation is correct, then the worst-case m you will need to achieve this will have you checking no more than 4n/k elements, so e.g. if k=100 you are much faster than checking all n elements. Then you know everything before A and everything after F are increasing sequences, and you can binary search through them. Now, if m got big enough that you checked at least sqrt(n) elements, then you can finish up by doing a brute-force search between A and F and the overall running time will be O(n/k + sqrt(n)). On the other hand, if the final m had you check fewer than sqrt(n) elements, then you can further increase m until you have checked sqrt(n) elements. Then there will be 2 pairs of consecutive checked elements (A,B),(C,D) that satisfy A < B, C > D, and there will also be 2 pairs of consecutive checked elements (W,X),(Y,Z) later in the array that satisfy W > X, Y < Z. Then everything before A is increasing, everything between D and W is decreasing, and everything after Z is increasing. So you can binary search these 3 regions in the array. The remaining part of the array that you haven't entirely searched through has size O(sqrt(n)), so you can use brute-force search the unchecked regions and the overall running time is O(sqrt(n)). Thus the bound O(n/k + sqrt(n)) holds in general. I have a feeling this is worst-case optimal, but I don't have a proof.

It's solvable in O(log^{2}n).

- if at midpoint the slope is decreasing we're in the
`p..q`

range. - if at midpoint the slope is increasing, we're either in
`1..p`

or in`q..n`

range.- perform a binary search in
`1.. mid point`

and`mid point..n`

ranges to seek for a value where the slope is decreasing. It will be found only in one of the ranges. Now we know in which of the`1..p`

and`q..n`

subranges the mid point is located.

- perform a binary search in
- repeat the process from (1) for the subrange with the peaks until hitting the
`p..q`

range. - find the peaks in the subranges by applying algorithm in Divide and conquer algorithm applied in finding a peak in an array.
- perform 3 binary searches in the ranges 1..p, p..q, q..n.

==> Overall complexity is O(log^{2}n).

Similar Questions

I have a getSortedIndex function. The function accepts the following arguments: An array of objects which are sorted by a key. A new object to be inserted into the array. The key by which all objects

Hello I just have a simple question, why is the big O notation of a sorted array O(log N)? It will be a sorted array.

I have this array: $categories = array( array('id' => 1, 'parent' => 0, 'name' => 'Category A'), array('id' => 2, 'parent' => 0, 'name' => 'Category B'), array('id' => 3, 'parent'

Is there a better way to search through $_SESSION variables (or any array) for a particular string than: foreach($_SESSION as $k => $v){ if(strstr($k, 'p_')){ Thanks. edit: My keys will look simil

This is a interview Question. Given a sorted array. Find the number of couples with the same difference. for example: if array is {1, 2, 3, 5, 7, 7 , 8, 9}; then we have 5 pairs with difference of 1

I need to store a few hundred strings in a data structure. Every string has two fields associated with it, like say word meaning and its origin.I can store the words in any fashion, say sorted,reverse

I have an array of items that are sorted by a key value, items are retrieved by doing a binary search. Simplified version of the items would look something like this: struct Item { uint64_t key; uint6

Is there an optimized function in any numerical library (MKL, Boost, GSL,..etc) that searches a sorted array of floating point numbers for the closest match to a given float? Another function which wi

I have a program that is searching a maze to find the best way out. As it searches it adds the next move to an array. My problem is that it keeps repeating the same three moves over and over. I need t

Given a sorted array of integers, can we build a sorted array of the sums of all pairs in O(n^2)? A trivial solution would be to build the array of sums in O(n^2) and then to sort it in O(n^2 (log(n^2

One of my array value contains $all_data_array = Array ( [0] => 'General Information' [1] => 'Brand' [2] => '<p><div style=bolor:#000000;><li>Product Details</li><

I have some problem with removing an element from a sorted array (all instances of an element must be removed). When I run my program, I get a segmentation fault. I have no idea why that happens, beca

Given an array @A we want to check if the element $B is in it. One way is to say this: Foreach $element (@A){ if($element eq $B){ print $B is in array A; } } However when it gets to Perl, I am thin

We know that several sorts, such as insertion sort, are great on arrays that are 'mostly-sorted' and not so great on random data. Suppose we wanted to profile the performance improvement/degradation o

what would be the most effective way to implement search for a string in sorted list of strings in Java? And what about searching for all the string beginning with part of a string? Thank you for help

I am creating an array and vector of size 100 and generating a random value and trying to maintain both array and vector as sorted. Here is my code for the same vector<int> myVector; int arr[SIZ

I'm working on sorted Queues like a Priority Queue. I already did it with a List, and it already worked great. Now I'd like to do it with a array. But I have a little logical Problem with add a new El

I came across this problem - input - I am given two sorted arrays a1 and a2. I need to find the elements that are not present in the second array. I have two approaches 1) Hashtable - O(m+n) [use whe

I'm putting together a search function that searches through multiple data attributes on a lot of divs on a page. Below is the code I have working for this. My problem I've come across is that it only

I'm trying to search through an array of arrays (17 rows and 26 columns) for one integer and print the index of that integer. For the sake of easy testing I've set the integer I'm searching for to 0,

I'm baffled that I can't find a quick answer to this. I'm essentially looking for a datastructure in Java which implements the java.util.List interface, but which stores its members in a sorted order.

I have a TStringList which is sorted and contains unique filenames. The list can be of any size (so it can be hundreds of thousands of entries). I want to check to see if any of the entries start with

I have to make a program in Java to create a sorted array in descending order. When i try to insert 10, 3 it is ok, but when i insert 10, 3, 8 the result is 10, 8, 0. For some reason the 0 appears on

My question regards the existence of a search algorithm for searching source code. In my project, I will have to implement an application that will search through a repository of source code (through

I'm looking for suggestions on algorithms / techniques for breadth first searching through an a streaming XML document. <foo> <bar name=aaa > <grah name=aab /> .. </bar> &

Is it possible to search for terms (such as method names) in .class files (from Referenced Libraries) in eclipse (I am able to view them automatically with JD Java Decompiler, so if I go through vario

I want to extend Array class so that it can know whether it is sorted (ascending) or not. I want to add a computed property called isSorted. How can I state the elements of the Array to be comparable?

How's it going folks---I'm having trouble iterating through an array in xcode--hoping someone can point me in the right direction..here's my response json response NSString *str=@jsonUrlremoved; NSU

This question already has an answer here: Need an algorithm for a special array (linear field) 3 answers I have tried the following code to find out the minimum element in a cyclic sorted array

Possible Duplicate: How do I randomly fill an array in Java? The last line of code below prints numbers in order. How to create an array where value are sorted randomly? List<Users> u = new A

How would I type up a code that searches through a text file from a given directory. I want the search word to be password123 and if it contains that, then it will proceed onto the next step, if not

I am looking for C algorithms (or code) that implement fast sorted integer array intersection/union operations. The faster, the better. In other words, what's an efficient way in C to implement union

NSSortDescriptor* sortOrder = [NSSortDescriptor sortDescriptorWithKey: @self ascending: NO]; NSLog(@%@,[ratio sortedArrayUsingDescriptors: [NSArray arrayWithObject: sortOrder]]); i sorted array b

I need to partially fill 2 arrays with data from a file and keep them parallel. But my current code gives me errors that look like giberish. If someone could even just help me decode the errors i woul

I found this question on an online forum: Really interested on how it can be solved: Given an array A of positive integers. Convert it to a sorted array with minimum cost. The only valid operation are

I am doing one exercise in Absolute Java. The Question is: Write a static method that has a partially filled array of characters as a formal parameter and that deletes all repeated letters from the ar

I'm new to STL, so please bear with me. I have an array of sorted vectors, vector< int> b[1000009]; Now I have to search the range between x and y inclusive in the row b[factor]. 'factor', 'x'

I have a log analysis script to populate a complex visualisation. Picture an array (called, rather unoriginally, 'log') of Activity objects, each of which is in the form: { name:foo, activities:[ {tim

I feel like this is a pretty easy question, but I can't seem to find the answer anywhere. $array = ('colors' => array('red','orange'), 'numbers'=> array('one','two') ); How do a perform a searc

I have an array of values which is almost, but not quite sorted, with a few values displaced (say, 50 in 100000). How to sort it most efficiently? (performance is absolutely crucial here and should be

I'm trying to work out how to continuously loop through an array, but apparently using foreach doesn't work as it works on a copy of the array or something along those lines. I tried: $amount = count(

Let's say you have two arrays of arrays with the same structure but different count of arrays in them: $arr1 = array(array(1,b), array(2,a), array(5,c)); $arr2 = array(array(3,e)); Now, the

Given a sorted but rotated array how do you find the pivot ? I was asked this question in an interview. What is a rotated array ? I got this on internet but its not clear at all. In a rotated sorted

We want to search for a given element in a circular sorted array in complexity not greater than O(log n). Example: Search for 13 in {5,9,13,1,3}. My idea was to convert the circular array into a regu

I have a document that I'm searching through for specific instances, however those instances are specified by the user and there are more than one. Other than a for loop inside a for loop searching a

I want to send an array to PHP through Ajax. array = $('.def-mask :checkbox:checked').serialize(); $.ajax({ url: 'ajax/battle.php', type: 'post', data: { playerReady: 1, attack: attack, defence: array

I have 2 arrays Array 1 : $agents = Array('abc','xyz','pqr'); Array 2 : $tot_calls = Array ('10','5','20'); Here array 2 reflects total calls made by agents in $agents array respectively. i.e Agent a

I'd like my array to be sorted by unique day and only show the day value once with all the times for that day included. Desired Example: Informal Monday: 2PM to 3PM, 3PM to 4PM, 4PM to 5PM Tuesday: 2

I have a two arrays of integers a = numpy.array([1109830922873, 2838383, 839839393, ..., 29839933982]) b = numpy.array([2838383, 555555555, 2839474582, ..., 29839933982]) where len(a) ~ 15,000 and le

I would like to write a piece of code for inserting a number into a sorted array at the appropriate position (i.e. the array should still remain sorted after insertion) My data structure doesn't allow