1,737 views
4 votes
4 votes
Consider an array ‘A’ with 2m elements. The elements in odd position are sorted in non-increasing order that is A[1] >= A[3] >= A[5]......A[2m-1] The elements in even position are sorted in non-decreasing order, that is A[2]<= A[4] <= A[6].....A[2m]. Which of the following method is recommended for finding if a given number is in array?

2 Answers

Best answer
9 votes
9 votes

The proper way to do is :

a) Implement binary search by a little modification in finding the middle index for both the 2 same sized subarrays..

b) If found , then report the element else continue recursively..

So the time complexity will be O(logm + logm)  = O(2logm) = O(logm) 

selected by
0 votes
0 votes
what i whould recommend is that seperate the give array into two arrays

1 elements in odd positions in non - increasing order

2. elements in even position in non - decreasing order

seperate this two arrays and store them in wo seperate arrays

and run the binary search on the both arrays  the time complexity will be

time to seperate and store in different arrays is n  (as they are n elements )

binary search (logm+logm)

Related questions

0 votes
0 votes
2 answers
1
dhruba asked Jun 5, 2023
1,089 views
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). ...
0 votes
0 votes
1 answer
2
Sabir Khan asked Aug 8, 2018
1,056 views
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is(A) (n)(B) (logn)(C) (log*n)(D) (1)
3 votes
3 votes
1 answer
3
iarnav asked Mar 13, 2018
1,938 views
The average successful search time taken by binary search on a sorted array of 5 CONSECUTIVE integers starting with 1?My Answer is - 2.2Kindly tell me is it correct or no...
3 votes
3 votes
2 answers
4
rahul sharma 5 asked Mar 8, 2018
2,359 views
Why to prefer binary search over ternary search?Can someone give recreance relation for ternary search,so that i can compare both