Question

6.)

(a) A string contains several X's followed by several O's. Devise a divide-and-conquer algorithim that finds the number of X's in the string in log₂n steps, where n is the length of the string.

(b) An array originally contained different numbers in ascending order but may have been subsequently rotated by a few positions. For example, the resulting array may be:

21 34 55 1 2 3 4 5 8 13

Is it possible to adapt the Binary Search algorithm for such data? Explain.

[Binary Search Algorithm below]

public class BinarySearch {

/**

* Uses Binary Search to look for target in an array a, sorted in ascending order. If found, returns the index of the matching element; otherwise returns -1.

*/

public static <T> int find(T[] a, Comparable<? super T> target) {

int left = 0, right = a.length - 1;

while (left <= right)

//Take the index of the middle element between "left" and "right":

int middle = (left + right) / 2;

//Compare this element to the target value and adjust the search range accordingly:

int diff = target.compareTo(a[middle]);

if(diff < 0)

right - middle - 1;

else if (diff > 0)

left = middle + 1;

else

return middle;

}

return -1;

}

}

Answer 1

6.

a)

As in our input, string S contains X's followed by O's

So we can use the below algorithm to find the last index of X, Which is the number of X's in S.

1. left = 1, right = length(Input string)
2. while( left < right )
3. { find middle = (left + right )/2
4. if ( S[middle] == 'O' )
5. then right = middle -1.
6. else
7. if ( S[middle]=='X' and S[middle+1]=='O')
8. return(middle) //middle is the last index of X
9. else
10. left = middle +1.
11. }

Here, in each iteration problem size is reduced by 2, So overall it takes log₂n steps.

b)

Yes, we can adapt the binary search algorithm, but before that, we have to find the pivot element such that the preceding element is greater than the pivot and the following element is smaller than the pivot.

Then dividing the array into two subarrays at pivot element, we can adapt the binary search algorithm on both subarrays to find some element.

And now how to find the pivot element:

• each time find the middle index and then check if the condition to be the pivot element is true or not.
• if true then stop and choose the middle element as pivot
• else repeat the first step to find pivot