Question

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

Answer 1

Answer:

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: