Binary Search in Java using Iteration and Recursion

Problem:

Create a binary search app in java using iteration and recursion.

Note: Binary search only works with sorted list of numbers.

Output:

Enter a target int
4
Target found iteratively!
Target found recursively!

Solution:

package binarySearchApp;

import java.util.Scanner;

public class BinarySearchApp {

 public static void main(String[] args) {
  int[] pool = {4,8,9,13,17,22};
  int target;
  Scanner scan = new Scanner(System.in);
  
  System.out.println("Enter a target int");
  target = scan.nextInt();
  boolean found;
  
//********************iterative version *************************   
  found = binarySearch_iter(pool, target);
  if (found) 
   System.out.println("Target found iteratively!");
  else
   System.out.println("Target not found iteratively!");
  
//********************recursive version ************************* 
  found = binarySearch_rec(pool, target, 0, pool.length-1);
  if (found) 
   System.out.println("Target found recursively!");
  else
   System.out.println("Target not found recursively!");
  
 }
 
//********************iterative method ************************* 
 private static boolean binarySearch_iter (int[] pool, int target) {
  
  int min = 0, max = pool.length-1, mid;
  boolean found = false;
  
  while (!found && min <= max) {
   mid = (min+max)/2;
   if (pool [mid] == target)
    found = true;
   else if (pool [mid] < target) 
    min = mid +1;
   else 
    max = mid -1;
   
  }
  return found;
 }

//********************recursive method ************************* 
 private static boolean binarySearch_rec (int[] pool, int target, int min, int max) {
  if (min > max)
   return false;
  else {
   int mid = (min + max)/2;
   if (pool[mid] == target)
    return true;
   else if (pool[mid] < target)
    return binarySearch_rec (pool, target, mid+1, max);
   else
    return binarySearch_rec (pool, target, min, mid-1);
  }
 }

}

Read More

Computer Fibonnaci Numbers with BigInteger in java

Problem:

Create a Fibonnaci program in java that calculate the fibbonaci numbers using BigInteger class. Include also iterative and recursive methods for the sake of comparaison.

Output:

Enter a positive int value (q to quit):
40
Iterative Fibonacci: 102334155
Recursion Fibonacci: 102334155
Duration: 2088
Accurate Fibonacci: 102334155
Enter a positive int value (q to quit):
q

Solution:

import java.math.BigInteger;
import java.util.Scanner;

public class FibonacciApp {

 public static void main(String[] args) {
  
  Scanner scan = new Scanner(System.in);
  int n;
  String n_str; 
  long fib_iter, fib_rec, time_in, time_out;
  BigInteger fib_acc;
  
  System.out.println("Enter a positive int value (q to quit):");
  n_str = scan.nextLine();
  
  while(!n_str.equalsIgnoreCase("q")) {
   try {
    n = Integer.parseInt(n_str);
    fib_iter = fibonacci_iter(n);
    System.out.println("Iterative Fibonacci: " + fib_iter);
    
    time_in = System.currentTimeMillis();
    
    fib_rec = fibonacci_rec(n);
    System.out.println("Recursion Fibonacci: " + fib_rec);
    
    time_out = System.currentTimeMillis();
    System.out.println("Duration: " + (time_out-time_in));
    
    fib_acc = fibonacci_acc(n);
    System.out.println("Accurate Fibonacci: " + fib_acc);
    
   } catch (NumberFormatException e) {
    System.out.println("Input must be numeric. Try Again");
   } 
   System.out.println("Enter a positive int value (q to quit):");
   n_str = scan.nextLine();
  }
  
  
 }
 
 private static long fibonacci_iter(int n) {
  
  if (n==0 || n==1) return n;
  else { 
   long previousprev = 0;
   long prev =1; 
   long current = 1L;
   
   for (int i=2 ; i <=n ; i++) {
   current = previousprev + prev; 
   previousprev = prev;
   prev = current;
   
   
   }
  return current;
  }
  
 }
 
 private static long fibonacci_rec(int n) {
  if (n ==0 || n==1 ) 
   return n;
  else 
   return fibonacci_rec(n-1)  + fibonacci_rec(n-2)
; }
 
 private static BigInteger fibonacci_acc(int n) {
  if (n==0 || n==1) 
   return BigInteger.valueOf(n);
  else {
   BigInteger prevprev = BigInteger.ZERO;
   BigInteger prev = BigInteger.ONE;
   BigInteger current = BigInteger.ONE;
   
   for (int i = 2; i <= n ; i++) {
    current = prevprev.add(prev);
    prevprev = prev;
    prev = current;
   }
   return current;
  }
 }
}

Read More

Convert from Decimal to Binary using Recursion in Java

Problem:

Write a method that converts from Decimal to Binary using Recursion in Java.

Output:

Not applicable.

Solution:

 public static void convert(int number)
  {
    if (number > 0)
    {
      convert(number / 2);
      System.out.print(number % 2);
    }
  }

Read More

Print Triangle using Recursion in Java

Problem:

Write a method that prints triangle using Recursion in Java.

Output:

Not applicable.

Solution:

import java.util.Scanner;
public class Stars 
{
    
    public static void main(String args[])
    {
      Scanner scan=new Scanner(System.in);
      System.out.println("enter the height of the triangle: ");
      int height=scan.nextInt();
      printTriangle(height);
    }
    
    public static String printTriangle (int count) {
    if( count <= 0 ) 
      return"";

        String p = printTriangle(count - 1);
        p = p + "*";
        System.out.print(p);
        System.out.print("\n");

    return p;
     }

  }

Read More

Find a String length Using Recursion in Java

Problem:

Write a method that finds the string length Using Recursion in Java

Output:

Not applicable.

Solution:

public class string_length_recursion
{
  public static int length (String str)
  {
    if (str == null || str.equals(""))
    {
      return 0;
    }
    
    else
      return 1 + length(str.substring(1));
  }
  
  public static void main(String[] args)
  {
    System.out.println(length("Few"));
  }
}

Read More

Compute GCD using three different methods in Java

Problem:

Compute GCD using three different methods in Java.

Output:

Not applicable.

Solution:

/**--------------------Method 1 ---------------*/
public class gcd_recursion_azzam
{
   public static int gcd(int m, int n, int i ) {
     
       if (m%i ==0 && n %i ==0)
         return i;
       else
         return gcd(m,n,--i);
  }
   
   public static void main(String[] args)
   {
     System.out.println(gcd(10,4,4));
   }
}
/**--------------------Method 2 ---------------*/
public class gcd_recursion_book
{
   public static int gcd(int m, int n) {
     
       if (m % n == 0) 
         return n;
       else if (m < n)
         return gcd(m,n);
       else
         return gcd(n, m%n);
     } 
   
   public static void main(String[] args)
   {
     System.out.println(gcd(10,4));
   }
}
/**--------------------Method 3 ---------------*/
public class gdc_recursion_online
{
   public static int gcd(int a, int b) {
     
       if (b==0) 
         return a;
       else
         return gcd(b, a % b);
     } 
   
   public static void main(String[] args)
   {
     System.out.println(gcd(10,4));
   }
}

Read More

Print a String Using Recursion in Java

Problem:

Print a string using recursion in Java.

Output:

Not Applicable.

Solution:

 public static void printchars(String str)
  {
    if(str == null || str.equals(""))
    {
      return;
    }
    
    else
    {
      System.out.print(str.charAt(0));
      printchars(str.substring(1));
    }
  }

Read More

Reverse a string using Recursion in Java

Problem:

Write a program that reverses a string using Recursion in Java

Output:

Not applicable.

Solution:

 public static void printcharsReverse(String str)
  {
    if (str == null || str.equals(""))
      return;
    else
      System.out.println(str.charAt(str.length() -1));
      printCharReverse(str.substring(0,str.length() - 1));
  }

Read More

Recursive Power Method in Java

Problem:

Write a recursive power method in Java.

Output:

Not applicable.

Solution:

public class x_y_power
{
  public static int power(int x, int y)
  {
    if (y == 0)
      return 1;
    
    else 
      return x*power(x , y - 1);
  }

Read More

Java Method that returns sum of 1 to Num

Problem:

Write a Java method that returns sum of 1 to Num.

Output:

Not applicable.

Solution:

public int sum ( int num) 
{ 
 int result; 
 if (num == 1) 
 result = 1; 
 else
 result = num + sum (num-1); 
 return result; 
}

Read More

Tower of Hinaoi java Method

Problem:

Write a Tower of Hinaoi Java Method.

Output:

Not applicable.

Solution:

public static void moveDisks(int n, char fromTower,  char toTower, char auxTower) {
if (n == 1) // Stopping condition
 System.out.println("Move disk " + n + " from " +
 fromTower + " to " + toTower);
 else {
 moveDisks(n - 1, fromTower, auxTower, toTower);
 System.out.println("Move disk " + n + " from " +
 fromTower + " to " + toTower);
 moveDisks(n - 1, auxTower, toTower, fromTower);
 } } }

Read More

Binary search method for an array in java.

Problem:

Writing a binary search method for an array in java.

Output:

Not applicable.

Solution:

// Returns the index of an occurrence of the given value in
// the given array, or a negative number if not found.
// Precondition: elements of a are in sorted order
public static int binarySearch(int[] a, int target) {
return binarySearch(a, target, 0, a.length - 1);
}
// Recursive helper to implement search behavior.
private static int binarySearch(int[] a, int target,
int min, int max) {
if (min > max) {
return -1; // target not found
} else {
int mid = (min + max) / 2;
if (a[mid] < target) { // too small; go right
return binarySearch(a, target, mid + 1, max);
} else if (a[mid] > target) { // too large; go left
return binarySearch(a, target, min, mid - 1);
} else {
return mid; // target found; a[mid] == target
}
}
}

Read More

Binary search method an array using Comparable in Java

Problem:

Write a methoe that binary search an array using Comparable in Java.

Output:

Not applicable.

Solution:

public static int binarysearch(Comparable[] items, Comparable target, int first, int last)
  {
    if(first>last)
      return -1;
    else
    {
      int middle=(first+last)/2;
      int value=target.compareTo(items[middle]);
      if(value==0)
        return middle;
      else if(value>0)
        return binarysearch( items,  target,  middle+1,  last);
      else
        return binarysearch( items,  target,  first ,  middle-1);

    }

Read More

Binary search an array using Comparable in Java

Problem:

Write a java program that uses binary search to search array
using Comparable in Java

Output:

Not applicable.

Solution:

public class Linearsearch
{
  public static void main(String[] args)
  {
    String[] stuff={"a","b","c"};
    System.out.println(linearsearch(stuff,"b", 0));
    System.out.println(binarysearch(stuff,"a", 0, stuff.length-1));
  }
  public static int linearsearch(Comparable[] items, Comparable target, int posfirst)
  {
    if(posfirst==items.length)
      return -1;
    else if(items[posfirst].compareTo(target)==0)
    {
      return posfirst;
    }
    else
      return linearsearch(items, target,  (posfirst+1));
  }

Read More

Sorting an array using recursion in java

Problem:

Write an method that sorts an array using recursion in Java

Output:

Not applicable.

Solution:

public static void sort(double[] list) {
  sort(list, list.length - 1);
  }
 
  public static void sort(double[] list, int high) {
  if (high > 1) {
  // Find the largest number and its index
  int indexOfMax = 0;
  double max = list[0];
 for (int i = 1; i <= high; i++) {
 if (list[i] > max) {
 max = list[i];
 indexOfMax = i;
 }
 }
 // Swap the largest with the last number in the list
 list[indexOfMax] = list[high];
 list[high] = max;
 // Sort the remaining list
 sort(list, high - 1);
 }

Read More

Recurive palindrome method using helper methods.

Problem:

Write a recursive palindrome method using helper methods to avoid creating new strings.

Output:

Not applicable

Solution:

public static boolean isPalindrome(String s) {
  return isPalindrome(s, 0, s.length() - 1);
 }
 
  public static boolean isPalindrome(String s, int low, int high) {
  if (high <= low) // Base case
  return true;
  else if (s.charAt(low) != s.charAt(high)) // Base case
  return false;
 else
 return isPalindrome(s, low + 1, high - 1);
 }

Read More

Check palindrome using recursion in java

Problem:

Write a recursion boolean method that checks if a string is a palindrome.

Output:

Not applicable.

Solution:

public static boolean isPalindrome(String s) {
if (s.length() <= 1) // Base case
return true;
 else if (s.charAt(0) != s.charAt(s.length() - 1)) // Base case
 return false;
 else
 return isPalindrome(s.substring(1, s.length() - 1));
  }

Read More

Finding Fibbonaci using Recursion in Java

Problem:

Write a recursive method that finds fibbonaci numbers in Java.

Output:

None.

Solution:

if (index == 0)
return 0;
else if (index == 1)
return 1;
else
return fib(index - 1) + fib(index - 2);

Read More

Finding Factorials Using Recursion in Java

Problem:

Write a recursive method that find factorials in Java.

Output:

None

Solution:

public class Factorial
{
  public static int factorial(int n)
  {
    if (n == 0)
      return 1;
        else
      return n * factorial(n - 1);
  }
}

Read More

Finding Prime Numbers Using Recursion in Java

Problem:

Write a recursive method that find finds prime numbers.

Output:

None.

Solution:

  public class TestPrime {
    public static void main(String[] args) {
    for (int i =2; i <100; i++)
    System.out.println("integer:" + i + " is prime:" + isPrime(i, i/2));

    }

    private static boolean isPrime(int n, int div) {
    if (div == 1)
    return true;
    else if (n%div==0)
    return false;
    else
    return isPrime(n, div - 1);
    }

  }

Read More