Implement a method that will search a given array using the linear search algori

Question

Implement a method that will search a given array using the linear search algorithm and a recursive binary search algorithm in Java.

Test the program for array sizes N = 16, 32, 64, 128, 256, 512, 1024, 2048, ......, 225. Initialize the array with random numbers between the ranges 1 through N and use the same array for testing linear search and binary search. Remember to sort the array before using binary search. Use a text file with 1,000 random numbers in the range 1 through 225 as the search keys.

Compare the execution time for linear search and binary search. Include the time taken for sorting with the binary search time (you have to sort only once for each array size).

Explanation / Answer

this is the example code useful for it

public class BinarySearch {

private static int list[] = {3, 6, 7, 8, 9, 10};

public static void main(String[] args) {
BinarySearch b = new BinarySearch();
b.binarySearch(list);

}

public void binarySearch(int[] args) {
System.out.println("Binary search.");

int upperBound = args.length;
int lowerBound = 1;
int midpoint = (upperBound + lowerBound) / 2;
int difference = upperBound - lowerBound;

int search = 7;

for (int i = 0; i < args.length; i++) {
if (search < args[midpoint - 1] && difference != 1) {
upperBound = midpoint - 1;
midpoint = upperBound / 2;
} else if (search > args[midpoint - 1] && difference != 1) {
lowerBound = midpoint + 1;
midpoint = (lowerBound + upperBound) / 2;

} else if (search == args[midpoint - 1]) {
midpoint = midpoint - 1;

System.out.println("We found " + search + " at position " + midpoint + " in the list.");
i = args.length;
} else {
System.out.println("We couldn't find " + search + " in the list.");
i = args.length;
}
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.