Dark Mode

1,293 views

12 votes

You are given a array $A$ of size $n$. Your are told that $A$ comprises three consecutive runs - first a run of $a$'s, then a run of $b$'s and finally a run of $c$'s. Moreover, you are provided an index of $i$ such that $A[i] = b$. Design an $O(\log n)$ time algorithm to determine the number of $b$'s (i.e., length of the second run) in $A$.

18 votes

Best answer

Hint: Modify Binary Search.

Solution:

You should use binary search twice first to find the first occurrence of $b$. Then apply it again to find the last occurrence.

The following code does this.

**BinarySearchForFirst**

int binarySearchForFirst(int l, int r){ int mid; while(l <= r){ mid = l+(r-l)/2; if(array[mid]=='b' && array[mid-1]=='a' ){//the desired case return mid; } if(array[mid-1]=='b'){//we're to the right of required index r = mid; continue; } if(array[mid]=='a'){//we're to the left or required index l = mid; continue; } } }

This returns the first index say $i$

Similarly find the second index $j$.

Then the answer is $j-i+1$

14 votes

The array looks something like this.

a.......a b...........b c.......c

We are provided an index of i such that A[i] = b

But that is which b ? Is that the first b ? Is that the last b ? Is that the middle b ? We do not know.

So we are given index to 'b'

Now do binary search in it's left & right side for 'b'

In left side binary search, if you found 'a' then move right, else move left .

In this way you can find the first b.

Similarly in right side of index i, up to index n, do a binary search for b,

if you found c, then move left otherwise move right.

In this way you can find the last b.

*(You know how we do binary search by finding mid which is (high+low)/2 )*

Now subtract the index of first b from last b. Thats it.