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

how to index odd and even places unique way? i mean what is indexing method ??

---

Hint: Whenever you index into the array using the value $\text{mid}$, use $2 \times \text{ mid}$ to binary search the even positions, and use $2 \times \text{ mid } + 1$ to binary search the odd positions.

In case the hint doesn't help much, let me know and I will give you the pseudocode.

---

does (2 x mid + 1 ) and ( 2  x mid -1) is same .... wen we consider odd position or , whether it should be 2mid plus 1??

---

That depends on where you're starting your indexing from. If your implementation of binary search can create a minimum value of $0$ for $\text{mid}$, then you need to use $2 \times \text{ mid } + 1$. If however your implementation creates a minimum value of $1$ for $\text{mid}$, you need to use $2 \times \text{ mid } - 1$.

Instead of figuring it out mentally, try implementing the algorithm. Implementing it will make things clear.

---

@arjun sir how  the space complexity is O(1) here

i think:

as each time we have to store two values for comparision  one for mid value of odd and one for even.and we will repeat untill base condition or loop to exit...which will be logn

---

@asu we are not doing a recursive calls. So, the space can be reused $\lg n$ times - no need of separate $\lg n $ space.

---

means u want to say...in this problem we are not doing recursive calls that's why it is O(1)..

what do u mean by this"So, the space can be reused lgnlg⁡n times - no need of separate lgnlg⁡n space.

---

pragy can you give pseudo code for this

---

HI Praggy,

Can you please provide the pseudo code

---

Plz correct me if I am wrong.

I dont think the given input will give the worst case of Quicksort , then how we are getting its time complexity as O(n^2)

---

do{
    int i=1;int j=2n;
    mid=(i+j)/2;
    if(a[mid+1]<num)
    i=mid+2;
    else{
        j=mid-2;
    }
}while(a[mid+1]!=num && m<n);
do{
    int m=2n;int n=1;
    mid=(m+n)/2;
    if(a[mid]>num)
    m=mid+1;
    else{
        n=mid-1;
    }
}while(a[mid]!=num && i<j);

There will be two loops

 

---

void binarySearchIterativeModified(int a[], int n, int x) {
	int i, j, k, midOdd, midEven;
	
	i = 0;
	j = n/2;
	while(i <= j) {
		k = (i+j) / 2;
		
		midOdd = (2*k) + 1;
		if(a[midOdd] == x) {
			printf("%d is found at %d index position.", x, midOdd);
			return;
		} else if(a[midOdd] < x) {
			i = k + 1;
		} else {
			j = k - 1;
		}
	}
	/* The elements in odd indices are already sorted in increasing order. 
	Above loop searches for elements in the odd indices. If found, it 
prints the corresponding index and returns. */
	
	i = 0;
	j = n/2;
	while(i <= j) {
		k = (i+j) / 2;
		
		midEven = (2*k);
		if(a[midEven] == x) {
			printf("%d is found at %d index position.", x, midEven);
			return;
		} else if(a[midEven] < x) {
			j = k - 1;
		} else {
			i = k + 1;
		}
	}
	/* The elements in even indices are already sorted in decreasing order.
	Above loop searches for elements in the even indices. If found, it 
prints the corresponding index and returns. */
	
	printf("%d is not found anywhere.", x);
	return;
	/* If element is not found either in odd or even indices, simply print
	error message and return. */
}

 

---

@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).