in java (a) Write a recursive function string reverse(string s) which uses the f
ID: 3723745 • Letter: I
Question
in java
(a) Write a recursive function string reverse(string s) which uses the following recursive strategy: reverse all but the first character of the string, and then concatenate the first character onto it appropriately. Recall that you can add a string and character together using the + operator.
(b) Rewrite this function using this alternative strategy: divide the string in half, reverse each half and the concatenate them appropriately.
(c) Rewrite the recursive binary search routine as a non-recursive method.
Explanation / Answer
import java.util.Arrays;
import java.util.Scanner;
public class My_problem {
//solution to part a
String rec_reverse_Strategy_1(String s,int i,int j){
String ret=null;
if(i==j)
{ret=s.charAt(i)+"";
return ret;
}
else if(i==j-1)
{
ret=s.charAt(j)+""+s.charAt(i);
return ret;
}
return rec_reverse_Strategy_1(s,i+1,j)+s.charAt(i);
}
//solution to part b
String rec_reverse_Strategy_2(String s,int i, int j)
{String ret=null;
if(i==j)
{ret=s.charAt(i)+"";
return ret;
}
else if(i==j-1)
{
ret=s.charAt(j)+""+s.charAt(i);
return ret;
}
String left_rev= rec_reverse_Strategy_2(s,i,(i+j)/2);
String right_rev=rec_reverse_Strategy_2(s,((i+j)/2)+1,j);
ret=right_rev+left_rev;
return ret;
}
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
System.out.println("enter the string to reverse using method 1:");
String s=sc.nextLine();
My_problem m=new My_problem();
s=m.rec_reverse_Strategy_1(s, 0, s.length()-1);
System.out.println( "String is reversed using first method,reversed string is: "+s);
System.out.println("enter the string to reverse using method 2:");
s=sc.nextLine();
s=m.rec_reverse_Strategy_2(s, 0, s.length()-1);
System.out.println("String is revered using second method,reversed string is: "+s );
//solution to part c
int n=0;
System.out.println("*****performing non recursive binary search***** ");
System.out.println("Enter number of elements:");
n=sc.nextInt();
int arr[]=new int[n];
System.out.println("enter elements:");
for(int i=0;i<n;i++)
arr[i]=sc.nextInt();
Arrays.sort(arr);
int key=-1,flag=-1;
System.out.println("enter element to search:");
key=sc.nextInt();
int i=0,j=arr.length-1;
while(i!=j)
{int mid=(i+j)/2;
if(arr[mid]==key)
{flag=1;break;
}
else if(arr[mid]>key)
{j=mid;}
else
i=mid;
}
if(flag==1)
System.out.println("element "+key+" is present in the array");
else
System.out.println("element "+key+" is not present in the array");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.