1. Write a recursive method to determine if a character is in a list of characters in O (logN) time. Mathematically prove (as we did in class) that T (N) = O (logN). You can assume that this list is sorted lexicographically.

2. Write a function that determines if a string has the same number of 0's and 1's using a stack. The function must run in O (N) time. You can assume there already exists a stack class and can just use it

1)

public class BinarySearch {

/ / Returns index of x if it is present in arr[l ...

/ / r], else return - 1

int binarySearch (char arr[], int l, int r, char x)

{

if (r > = l) {

int mid = l + (r - l) / 2;

/ / If the element is present at the

/ / middle itself

if (arr[mid] = = x)

return mid;

/ / If element is smaller than mid, then

/ / it can only be present in left subarray

if (arr[mid] > x)

return binarySearch (arr, l, mid - 1, x);

/ / Else the element can only be present

/ / in right subarray

return binarySearch (arr, mid + 1, r, x);

}

/ / We reach here when element is not present

/ / in array

return - 1;

}

/ / Driver method to test above

public static void main (String args[])

{

BinarySearch ob = new BinarySearch ();

char arr[] = {'a','c','e','f','g','h'};

int n = arr. length;

char x = 'g';

int result = ob. binarySearch (arr, 0, n - 1, x);

if (result = = - 1)

System. out. println ("Character not present");

else

System. out. println ("Character found at index " + result);

}

}

2)

import java. io.*;

import java. util.*;

public class Test{

public static boolean checksame (String s)

{

Stack stack = new Stack ();

for (int i=0; i
{

if (s. charAt (i) = ='0')

{

if (stack. empty () = =false)

{

if ((Integer) stack. peek () = =1)

stack. pop ();

else

stack. push (0);

}

else

{

stack. push (0);

}

}

else if (s. charAt (i) = ='1')

{

if (stack. empty () = =false)

{

if ((Integer) stack. peek () = =0)

stack. pop ();

else

stack. push (1);

}

else

{

stack. push (1);

}

}

}

return stack. empty ();

}

public static void main (String []args) {

System. out. println (checksame ("a0w1220"));

}

}