ISI 2015 PCB C2 B

Question

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$.

Answer 1

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$

Comments

2nd index of j means last occurrence of b can be found out by finding 1st occurence of c right!

---

What about this method? Index of the first occurrence of 'c' - index of the first occurrence of 'b' + 1?

Complexity would still remain O(logn) right?

Answer 2

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.