recategorized by
983 views
3 votes
3 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?

  1.   Sort the given array using quick sort and then apply binary search on array.
  2.   Merge the sorted lists and apply binary search.
  3.   Apply binary search on the entire array.
  4.   Separately apply binary search on the odd position elements and even position elements

i thought answer would be B,cuz then O(n) time will be taken but answer is D.how can we apply binary search on odd and even seperatly..pls guide me

recategorized by

1 Answer

0 votes
0 votes
While we apply binary search separately we get the element’s id(if present) from any of 2 divided arrays.

Using binary search 2 times on m elements of  each array we get T.C as logm + logm

so t.c will be O(log n)

Related questions

8 votes
8 votes
2 answers
1
0 votes
0 votes
2 answers
2
dhruba asked Jun 5, 2023
1,090 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). ...
1 votes
1 votes
2 answers
4