ISI-2017-PCB-C6

Question

Let $A = \{a_1,a_2, \dots ,a_n\}$ be an array of $n$ distinct numbers. The array may not be sorted. The first element $a_1$ is said to be a blip if $a_1 > a_2$. Similar, the last element an is said to be a blip if $a_n > a_{n-1}$. Among the remaining elements, an element $a_i$ is said to be blip if $a_i > a_{i-1}$ and $a_i > a_{i+1}$ where $i \in (2,3, \dots ,n-1)$.  Design an $O(\log n)$ time algorithm for finding a blip in $A$. Justify the complexity of your algorithm.

Answer 1

Take the middle element if it is a blip then return it
Otherwise,

1. if the left element is greater than the middle element then there exist a blip in the left array
2. or if the right element is greater then there exist a blip in the right array.

Example:

If $A$ is  an array of size $n$ then the middle element of the array is the number $A[(n+1)/2]$ when $n$ is odd and the middle element of the array is $A[n/2]$ when $n$ is even.

Now, take the unsorted array $10,9,8,11,12,13,15,16,12$

Middle element in the array $→ 12$

• Left of middle  $11$ (smaller)
• Right of middle $13$ (greater)

So, blip present in the right array  $13,15,16,12$

Middle element of right array  15

• Right of middle $16$ (greater)
• Left of middle $13$ (smaller)

So, blip is present in the right array $16,12$

Middle $:16$

• Right of middle 12 (smaller)

So, $16$ is a blip.

This will hold for any unsorted array take more examples to verify it. The time complexity will be $O(\log n)$ as in each step we are reduing the problem size by at least half. 

Comments

Yeah I got it.

---

16 > 12 : no how?

---

@Kushagra Chatterjee Can you add some intuition behind this algo regarding why it works?

Answer 2

//given the array the below method returns the blip element if found otherwise null.

FIND_BLIP(A):

1. size  = A.length;
2. if(size == 0) return null;
3. else if(size == 1) return A[0];
4. else if(size == 2) return A[0] > A[1] ? A[0] : A[1];
5. else {
6.          int i = 1, j = size – 1;
7.          if(A[i-1] > A[i]) return A[i-1];
8.          else if (A[j] > A[j-1]) return A[j];
9.          else {
10.                 while(i <= j) {
11.                       int left = A[i-1], right = A[i+1], mid = i + (  j – i ) / 2;
12.                       if(A[mid] >  left && A[mid] > right) return A[mid];
13.                       else if(A[mid] > left) j = mid – 1;
14.                       else i = m + 1;
15.                 }
16.         }
17.  }
18. return null;