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<Integer> stack= new Stack<Integer>();

for(int i=0;i<s.length();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"));

}

}

Explanation:

by trying your best others ^_^

but don't try sending them fake answer, it must to be real answer.

the reason why you must not send them fake answer cause the experts and the questioner will moderate you and if they find out its fake they will report your to the owner of this website which its called

explanation: