Can an algorithm search a **combined 2 sorted array** in O( log(n) ) ??

**Combined 2 sorted array**:

Is a combination of 2 sorted arrays..

Example: {1,2,3,4,5} + {2,3,4,5,6,7,} = {1,2,3,4,5,2,3,4,5,6,7}

Unfortunately, you do not know the boundary of them

*Please note I know a solution that gives O( log(n) ) in amortized time, but I need that O( log(n) ) in only one search..

*Edit:* You can assume distinct elements

Thanks

I think in the worst case you have to examine each element of the combined array, which gives `O(n)`

worst-case complexity.

Here is the intuition: Let's say you've examined some subset of elements and have found them to be monotonically increasing with their position, and that the element you're looking for isn't present in the subset. There's absolutely nothing you can do to discard part of the search space, since the element -- regardless of its magnitude -- can still be validly located at *any* unexamined position. In the worst case this condition can remain true until you have examined the entire array.

No you can't.

Proof:

Take any sorted array. Change any one of the elements into an arbitrary, new value X. The result is now either a sorted array or a combined 2-sorted array. You have to search for X. Because X was inserted in a random location without any reference to the contents of the rest of the array, the only way to find X is by brute force.

Similar Questions

I know that the definition of suffix array itself is that its a sorted array of all the suffixes of a string. But I am trying to understand whats the significance of this sorting operation here? Suppo

So, you have n sorted arrays (not necessarily of equal length), and you are to return the kth smallest element in the combined array (i.e the combined array formed by merging all the n sorted arrays)

Hey guys i'm trying to use drawString() function to draw the result from a search in a array. I am using the code below import java.awt.Graphics; public class canvas extends JPanel{ int i, count; publ

I have a 2 dimensinal dictionary representing people. Here's an example of it: >>> people = {'pk1':{'firstname':'Brian', 'age':42}, 'pk2':{'firstname':'Alex', 'age':50}} As can be seen, ther

I have this PHP code to fetch the mysql data: while ($row = $stmt->fetch(PDO::FETCH_ASSOC)) { // create an array for the results $menuItems['menu_items'][] = array( 'item_id' => $row['item_id'],

I need to access the array of sorted data after sorting a table since the original is unchanged. There is an gridOptions.ngGrid.filteredData but no gridOptions.ngGrid.sortedData How can I access the s

Suppose you have a sorted range (x to y) of values in an array. x = 3; y = 11; array == 3, 4, 5, 6, 7, 8, 9, 10, 11 But it is possible that some values are duplicated and some are missing, so you mig

I have a 2 dimensional array. The rows and columns are sorted. How to find the kth largest element from the 2-d array?

I have a PHPArray : $fullData = array ( array ( 'id' => 23123, 'name'=>'a', number =>...), array().... ); This full dataset is displayed to the user. However if he comes from a form page, I

What would be the smallest and largest number of comparisons in an unsorted array that could have duplicate elements as well ? I understand that finding anything in an unsorted array is a O(n) problem

have following problem. suppose i have an array number[n] , i want search multiple number , for example i want to search 12, 45 ,1 ,6,8,5, and if every number present array then i can get favorable re

Result holds dynamic value in array but after sorting the result also get sorted but I don't want it to get sorted. But after sorting its also get sorted. Why is that? $scope.arreyList = result; var s

I got a call from Amazon to attend one of their interview and given a test to write most efficient solution to the below problem. To find smallest position of 1 in sorted array of 0 and 1. e.g. in arr

I have a combined array, that is combining the news headline results of API1 and API2. How do I get the headline text from each object in the new combined array? Right now I have the app working fin

I am trying to binary search a 2D array which will give me the position of every key in the array, my code is #include <iostream> #include <vector> using namespace std; vector<pair<i

I needed to get some help with an array. I created one array of users with the field name of EmailAddresses and they are formatted as follows: {sip:jsmith@domain.com, SMTP:jsmith@domain.com, etc....

I have 2 time series that contain Bar objects, each Bar object contains a member variable of type long and each time series is stored within its own BlockingCollection. The time series is sorted in as

we got an increasing sorted multidimensional array for example: int[][] mat = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16}}; How can I use binary search to find a specific number? let's say im

Possible Duplicate: C# fastest intersection of 2 sets of sorted number What is the fastest way to union 2 sets of sorted values? Speed (big-O) is important here; not clarity - assume this is being d

I have a partially sorted tuple in Python 2.x. Why Python reverse it instead of sort it? >>> data = (u'a', (1,), 'b ', u'b', (2,), 'c ', u'c', (3,), 'd ', u'd', (4,), 'e') >>> sorted

I've written the following program to implement Binary Search of a sorted array: int flag=0; void binarysearch(int x, int a[], int m, int n) { int middle=(m+n)/2; if(a[middle]==x) { printf(%d has be

Possible Duplicate: Fastest strategy to form and sort an array of positive integers What would be the fastest way to get a sorted array from an unsorted iterable of integers ? Currently I do it by i

I have this numpy array where the values in each row will always be sorted and monotonically increasing: a = np.array([[1, 2, 3, 4, 8], [2, 5, 6, 7, 8], [5, 7, 11, 12, 13]]) and I want to search for

What is the time complexity to remove the smallest value from an array with n elements that is sorted from smallest to largest? I believe it is O(1) because the smallest value is the first value of th

I need to join data from 2 different table this tables are also from different databases. I need to join them in 1 Table. Here is the illustration: TABLE1 ---------- dr_no prd_sys_code ship_code 123 A

Suppose I have the following array $diff. a, a, a, a, b, b, b, a, a, b, b, b, a, a, a, b A represents a value inside $diff. B represents an Array inside $diff. Now I have to count A if it occurred mo

I'm doing a project in Java which includes (x,y) coordinates. I have created a class of Cell which has protected integers X & Y; Upon initialization, i do a for loop which sets an array of cell by

I'm new to PHP/sql, but I can't seem to figure out why this function isn't returning an appropriately sorted array. It's returning the right results, but they aren't sorted. //TAKE PRODUCT ID RETURN

I am developing a FAQ (Frequently Asked Question) PHP script and I want to implement a way for users to search the FAQs. This is a small script so I have the categories and FAQs in an array as shown b

This question already has an answer here: PHP - find entry by object property from a array of objects 3 answers I have an array of objects from class Volume. I am looking for the best way to re

I have this array (shortened for readability) array(10) { [0] => array(23) { [account_id] => int(4294967295)[player_slot] => int(0)[hero_id] => int(41)[item_0] => int(0)[item_

I was preparing for a competition and came across this question, which I can't comprehend. Consider a set of 'n' elements in an array, which is sorted except for one element that appears out of order.

I have an array of Sorted integers. We can use binary search to find an element . Now if one element of sorted array is interchanged with another element. What would be the best way to find the interc

We are given an array of numbers and we want to find a subsequence of size 4 that is sorted in increasing order. for eg ARRAY : -4 2 8 3 1 5 sorted subsequence of size 4 : -4 2 3 5 PS:There is a way

I want to sort two already sorted arrays into one. I am using merge sort for this purpose. Error:: IndexError: list index out of range I have tried checking out this manually and I couldnt find out of

Given an array where elements are sorted in ascending order,and I need convert it to a 2-3-4 tree I thought of a recursion which create every loop n/3 nodes, choosing the maximum, and now I'm having h

Is there a way to perform a partial sort on an array of data so that the last n elements are sorted? By good I mean using the standard library, not implementing my own sort function (this is what I'm

I'm trying to do an assignment for a class, and I'm pretty stuck here. What I need to do is search an array of doublewords for a specified doubleword value. Here's what I have now: ; DriverSub assembl

Today, I went for an interview and the interviewer asked me how I would find the index of a given value (number) in a pre-sorted array like this: $preSortedArr=array(23,32,36,41,45,54); He also said

I am learning ruby and was given the following assignment: given two sorted arrays like the following we must merge them into one sorted array. array_1 = [5,8,9,11] array_2 = [4,6,7,10] merge(array_1,

I'm trying to loop through an array and return the values sorted by a pattern (groups of two). My abstract math skills are failing me. I'm stumped, I can't figure out the pattern. Here's what I have s

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

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

Answering to another question, I wrote the program below to compare different search methods in a sorted array. Basically I compared two implementations of Interpolation search and one of binary searc

In bash I'have a sorted integer array like: array[0]=1 array[1]=2 array[2]=3 array[3]=4 array[4]=7 array[5]=9 array[6]=10 array[7]=13 array[8]=15 array[9]=16 And I want to obtain output like: 1-4,7,

I need to create a method that inserts an integer into a sorted array of integers. I had already done this method but not with integers but with strings. Now I have a problem with integers. My method

Given an infinite length sorted array having both positive and negative integers. Find an element in it. EDIT All the elements in the array are unique and the array in infinite in right direction. Th

I am getting values which are sorted from a plist and displaying them in a tableview. I am providing the capability of entering a custom category which will be written to plist. But I want that to be

I have an array like this in JS: var a = [1, 2, 1_10, 1_22, 2_12, 3, 14, 1_15, 3_31, 14_25, 2_18]; and I need to sort it, in order to look like this: [1, 1_10, 1_15, 1_22

Possible Duplicate: Interview Q: sorting an almost sorted array (elements misplaced by no more than k) I have a partially sorted array with the property that every element is within d units of its p