Write a program that a. Calls a method that takes two parameters, an integer and
ID: 3803810 • Letter: W
Question
Write a program that a. Calls a method that takes two parameters, an integer and an integer array. The call should perform binary search and should return the index of the integer in the array if found and should return -(insertionPoint+1) if the number is not found. Print out the index in the main method. b. Calls a second method that performs binary search recursively. It should take 4 parameters: 3 integers and an array of integers. It should return the index of the element if found, if not then it should return -1. Write a program that calls a method called selectionSort that accepts an integer array as a parameter and sorts the elements in the array using the selection sort algorithm. Print the array before it is sorted and after it is sorted.Explanation / Answer
1)
import java.util.Scanner;
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author Surya
*/
public class BinarySearch {
static int recursiveBinarySearch(int[] Array, int start, int end, int k)
{
if (start < end) {
int mid = start + (end - start) / 2;
if (k < Array[mid]) {
return recursiveBinarySearch(Array, start, mid, k);
} else if (k > Array[mid]) {
return recursiveBinarySearch(Array, mid+1, end , k);
} else {
return mid; //if found returning index
}
}
return -1; //if not found returning -1
}
static int iterativeBinarySearch(int[] Array, int k) {
int start = 0;
int end = Array.length - 1;
while (start <= end)//binary search
{
int mid = (start + end) / 2;
if (k == Array[mid]) {
return mid;//if found returning index
}
if (k < Array[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -(start + 1);//if not found returning insertion point -1
}
public static void main(String argv[])
{
int n;//variable declaration
Scanner sc = new Scanner(System.in);
//prompting input...
System.out.print("Enter list length:");
n=sc.nextInt();
//reading list..
int i,a[]=new int[n];
System.out.println("Enter list in sorted order :");
for(i=0;i<n;i++)
{
a[i]=sc.nextInt();//reading list
}
System.out.println("Iterative BinarySEARCH : ");
int s,l;//element to search
System.out.print("Enter element to search:");
s=sc.nextInt();
l=iterativeBinarySearch(a,s);//function calling
if(l>=0)
{System.out.println("Found at index :"+l);
}
else
{
System.out.println("NOt Found,to be inserted at position :"+l);
}
//calling again
System.out.println("Iterative BinarySEARCH : ");
System.out.print("Enter element to search:");
s=sc.nextInt();
l=iterativeBinarySearch(a,s);//function calling
if(l>=0)
{System.out.println("Found at index :"+l);
}
else
{
System.out.println("NOt Found,to be inserted at index :"+l);
}
//recursive binary search
System.out.println("Recursive BinarySEARCH : ");
System.out.print("Enter element to search:");
s=sc.nextInt();
l=recursiveBinarySearch(a,0,n,s);//function calling
if(l>=0)
{System.out.println("Found at index :"+l);
}
else
{
System.out.println("NOt Found :"+l);
}
//calling agian
System.out.println("Recursive BinarySEARCH : ");
System.out.print("Enter element to search:");
s=sc.nextInt();
l=recursiveBinarySearch(a,0,n,s);//function calling
if(l>=0)
{System.out.println("Found at index :"+l);
}
else
{
System.out.println("NOt Found :"+l);
}
}
}
output:-
run:
Enter list length:5
Enter list in sorted order :
1
3
4
6
9
Iterative BinarySEARCH :
Enter element to search:4
Found at index :2
Iterative BinarySEARCH :
Enter element to search:10
NOt Found,to be inserted at position :-6
Recursive BinarySEARCH :
Enter element to search:9
Found at index :4
Recursive BinarySEARCH :
Enter element to search:1
Found at index :0
BUILD SUCCESSFUL (total time: 1 minute 4 seconds)
2)
import java.util.Scanner;
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author Surya
*/
public class SelectionSort {
static void Selection_Sort(int[] array){
//sorting arrayay using selection sort procedure
for (int i = 0; i < array.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < array.length; j++)
if (array[j] < array[index])
index = j;
int smallerNumber = array[index];
array[index] = array[i];
array[i] = smallerNumber;
}
}
public static void main(String argv[])
{
int n;//variable declaration
Scanner sc = new Scanner(System.in);
//prompting input...
System.out.print("Enter list length:");
n=sc.nextInt();
//reading list..
int i,a[]=new int[n];
System.out.println("Enter list:");
for(i=0;i<n;i++)
{
a[i]=sc.nextInt();//reading list
}
//printing arrayay before sorting.
System.out.println("Array before sorting");
for(i=0;i<n;i++)
{
System.out.print(a[i]+" ");
}
System.out.println();
//calling sorting function
Selection_Sort(a);
//printing array after sorting
System.out.println("Array after sorting:");
for(i=0;i<n;i++)
{
System.out.print(a[i]+" ");
}
System.out.println();
}
}
output:-
run:
Enter list length:5
Enter list:
4
9
72
6
8
Array before sorting
4 9 72 6 8
Array after sorting:
4 6 8 9 72
BUILD SUCCESSFUL (total time: 12 seconds)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.