import java.util.Scanner;
	
public class linearSearch {
	private static int[] array = new int[9];
	 
	  public static void main(String args[])
	  {
	    
	    Scanner in = new Scanner(System.in);
	    for(int i=0; i<array.length; i++) {
	    	System.out.println("Enter number " + (i+1) +":");
	    	array[i]=in.nextInt();
	    }
	    System.out.println("Iterative or Recursive Linear Search?");
	    if(in.hasNextLine()) {
	    if (in.nextLine().equalsIgnoreCase("Recursive")) {
	    	System.out.println("Recursive");
	    	System.out.println("Enter number to search for:");
			   int searchedNumber=in.nextInt();
			   linearSearchRecursive(searchedNumber, 0);
	    }
	    else if (in.nextLine().equalsIgnoreCase("Iterative")){
	    	System.out.println("Iterative");
	    	System.out.println("Enter number to search for:");
	    	 int searchedNumber=in.nextInt();
	    	linearSearchIterative(searchedNumber);
	    }
	    }
	  }
	  
	  public static int linearSearchRecursive(int searchedNumber, int n) { 
		  if(n==array.length) {
			  System.out.println("Number could not be found");
			  return -1;
		  }
		  if(array[n]==searchedNumber) {
		   System.out.println("found" + searchedNumber + "at index " + n);
		   return n;
	   }
	   else {
		   return linearSearchRecursive(searchedNumber, n+1);
	   }
	   }
	  
	  public static void linearSearchIterative(int searchedNumber) {
		   for(int j=0; j<array.length; j++) {
			   if (array[j]==searchedNumber) {
				   System.out.println("found number at index " + j);
				   return;
			   }
		   }
		  }
}