Answers
Complete Program:
// File: search.java
import java.util.Random;
import java.util.Scanner;
public class search
{
public static int Seq_search(int[] arr, int target)
{
for(int i = 0; i < arr.length; i++)
{
if(arr[i] == target)
return i;
}
return -1;
}
public static void Sel_sort(int[] arr)
{
for(int i = 0; i < arr.length - 1; i++)
{
int minPos = i;
for(int j = i + 1; j < arr.length; j++)
{
if(arr[minPos] > arr[j])
{
minPos = j;
}
}
if(i != minPos)
{
int temp = arr[i];
arr[i] = arr[minPos];
arr[minPos] = temp;
}
}
}
public static int Bin_search(int[] arr, int target)
{
int first = 0;
int last = arr.length - 1;
while(first <= last)
{
int middle = (first + last) / 2;
if(arr[middle] == target)
return middle;
if(arr[middle] < target)
first = middle + 1;
else
last = middle - 1;
}
return -1;
}
public static int BinRe_search(int[] arr, int target)
{
return BinRe_search(arr, 0, arr.length - 1, target);
}
private static int BinRe_search(int[] arr, int first, int last, int target)
{
if(first > last)
return -1;
int middle = (first + last) / 2;
if(arr[middle] == target)
return middle;
if(arr[middle] < target)
return BinRe_search(arr, middle + 1, last, target);
else
return BinRe_search(arr, first, middle - 1, target);
}
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
Random rand = new Random();
System.out.print("Enter the size of the arrays: ");
int size = input.nextInt();
while(size <= 100)
{
System.out.print("Enter the size of the arrays > 100: ");
size = input.nextInt();
}
int A[] = new int[size];
int B[] = new int[size];
int C[] = new int[size];
for(int i = 0; i < size; i++)
{
int number = 1 + rand.nextInt(99);
A[i] = number;
B[i] = number;
C[i] = number;
}
long before, after, elapsed;
int idx1, idx50, idx100;
// test for sequential search
before = System.nanoTime();
idx1 = Seq_search(A, 1);
after = System.nanoTime();
elapsed = after - before;
if(idx1 > -1)
System.out.println("\n1 is found at the index " + idx1 + " in the array. Sequential Search has done in " + elapsed + " nanoseconds.");
else
System.out.println("\n1 is not found in the array. Sequential Search has done in " + elapsed + " nanoseconds.");
before = System.nanoTime();
idx50 = Seq_search(A, 50);
after = System.nanoTime();
elapsed = after - before;
if(idx50 > -1)
System.out.println("50 is found at the index " + idx50 + " in the array. Sequential Search has done in " + elapsed + " nanoseconds.");
else
System.out.println("50 is not found in the array. Sequential Search has done in " + elapsed + " nanoseconds.");
before = System.nanoTime();
idx100 = Seq_search(A, 100);
after = System.nanoTime();
elapsed = after - before;
if(idx100 > -1)
System.out.println("100 is found at the index " + idx100 + " in the array.
Sequential Search has done in " + elapsed + " nanoseconds.");
else
System.out.println("100 is not found in the array. Sequential Search has done in " + elapsed + " nanoseconds.");
// test for binary search
before = System.nanoTime();
Sel_sort(B);
after = System.nanoTime();
elapsed = after - before;
System.out.println("\nSorting has done in " + elapsed + " nanoseconds.");
before = System.nanoTime();
idx1 = Bin_search(B, 1);
after = System.nanoTime();
elapsed = after - before;
if(idx1 > -1)
System.out.println("1 is found at the index " + idx1 + " in the array. Binary Search has done in " + elapsed + " nanoseconds.");
else
System.out.println("1 is not found in the array. Binary Search has done in " + elapsed + " nanoseconds.");
before = System.nanoTime();
idx50 = Bin_search(B, 50);
after = System.nanoTime();
elapsed = after - before;
if(idx50 > -1)
System.out.println("50 is found at the index " + idx50 + " in the array. Binary Search has done in " + elapsed + " nanoseconds.");
else
System.out.println("50 is not found in the array.
Binary Search has done in " + elapsed + " nanoseconds.");
before = System.nanoTime();
idx100 = Bin_search(B, 100);
after = System.nanoTime();
elapsed = after - before;
if(idx100 > -1)
System.out.println("100 is found at the index " + idx100 + " in the array. Binary Search has done in " + elapsed + " nanoseconds.");
else
System.out.println("100 is not found in the array. Binary Search has done in " + elapsed + " nanoseconds.");
// test for recursive binary search
before = System.nanoTime();
Sel_sort(C);
after = System.nanoTime();
elapsed = after - before;
System.out.println("\nSorting has done in " + elapsed + " nanoseconds.");
before = System.nanoTime();
idx1 = BinRe_search(C, 1);
after = System.nanoTime();
elapsed = after - before;
if(idx1 > -1)
System.out.println("1 is found at the index " + idx1 + " in the array. Recursive Binary Search has done in " + elapsed + " nanoseconds.");
else
System.out.println("1 is not found in the array. Recursive Binary Search has done in " + elapsed + " nanoseconds.");
before = System.nanoTime();
idx50 = BinRe_search(C, 50);
after = System.nanoTime();
elapsed = after - before;
if(idx50 > -1)
System.out.println("50 is found at the index " + idx50 + " in the array.
Recursive Binary Search has done in " + elapsed + " nanoseconds.");
else
System.out.println("50 is not found in the array. Recursive Binary Search has done in " + elapsed + " nanoseconds.");
before = System.nanoTime();
idx100 = BinRe_search(C, 100);
after = System.nanoTime();
elapsed = after - before;
if(idx100 > -1)
System.out.println("100 is found at the index " + idx100 + " in the array. Recursive Binary Search has done in " + elapsed + " nanoseconds.");
else
System.out.println("100 is not found in the array. Recursive Binary Search has done in " + elapsed + " nanoseconds.");
}
}
Sample Output:
From the Sample Output, Bin_search() method takes the least amount of time to search an elelemt in an array. So Bin_search() method is better than Seq_search() and BinRe_search() methods.
.