TIFR CSE 2010 | Part B | Question: 29

Question

Suppose you are given an array $A$ with $2n$ numbers.

The numbers in odd positions are sorted in ascending order, that is, $A[1] \leq A[3] \leq \ldots \leq A[2n - 1]$.

The numbers in even positions are sorted in descending order, that is, $A[2] \geq A[4] \geq \ldots \geq A[2n]$.

What is the method you would recommend for determining if a given number is in the array?

• A. Sort the array using quick-sort and then use binary search.
• B. Merge the sorted lists and perform binary search.
• C. Perform a single binary search on the entire array.
• D. Perform separate binary searches on the odd positions and the even positions.
• E. Search sequentially from the end of the array.

Comments

worst case scenario of selection sort.

sine wave input

---

Time complexities.

1. Sort the array using quick-sort and then use binary search.  O(n^2) 
2. Merge the sorted lists and perform binary search.    O(n)
3. Perform a single binary search on the entire array.   O(logn)  (but can’t apply here)
4. Perform separate binary searches on the odd positions and the even positions. O(logn)
5. Search sequentially from the end of the array.   O(n)

Space complexities.

1. Sort the array using quick-sort and then use binary search.  O(logn) 
2. Merge the sorted lists and perform binary search.    O(n)
3. Perform a single binary search on the entire array.   O(1)  (but can’t apply here)
4. Perform separate binary searches on the odd positions and the even positions. O(1)
5. Search sequentially from the end of the array.   O(1)

Anyone confirm this... 

Answer 1

Option D is the correct answer.

We can simply use clever indexing to binary search the element in the odd positions, and in the even positions separately.

This will take $O(\log n)$ time and $O(1)$ space in the worst case.

A: Sorting using Quicksort will take $O(n^2)$ time.
B: Merging will take $O(n)$ time and $O(n)$ space.
C: Binary search only works on a sorted array.
E: Sequential search will take $O(n)$ time.

Comments

@srestha 

if (n%2=0)

{

binary search on even index

}

else

{

binary search on odd index

}

This pseudo code also perform in single binary search...am i correct ma'am

---

The complexity with the merge sort will be $\mathbf{O(\log n) + O(n)}$.

$\mathbf{O(n)}$ to merge and $\log n$ for binary search.

Therefore, D is the best option only.

---

@JEET

The complexity with the merge sort will be O(logn)+O(n).

Don’t use the sort here otherwise it will be O(nlogn).