Estimate and Measure two search methods, one on the linked lists and the second
ID: 3785412 • Letter: E
Question
Estimate and Measure two search methods, one on the linked lists and the second one on the sorted arrays.
How to measure running time. (Depends on the size of your input).
Returns current time in milliseconds:
static long System.currentTimeMillis()
Returns current time in nanoseconds: static long System.nanoTime()
Directions:
Create two search methods that search for a given value and return its index if found, or -1 otherwise.
For each of the methods estimate its complexity theoretically. Use Big-Theta for your answer. You need to find the best algorithm possible. Hint: One method will be more efficient that another.
Explanation / Answer
Hi, Please find my implementation.
Please let me know in case of any issue.
import java.util.LinkedList;
import java.util.Random;
import java.util.Scanner;
public class SearchTimeComplexity {
// binary search for sorted array
public static int binarySearch(int[] inputArr, int key) {
int start = 0;
int end = inputArr.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (key == inputArr[mid]) {
return mid;
}
if (key < inputArr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
// linear search for linked list
public static int linearSearch(LinkedList<Integer> list, int key){
for(int i=0; i<list.size(); i++){
if(list.get(i) == key)
return i;
}
return -1;
}
public static void main(String[] args) {
// creating linked list and array and filling with 5000 random numbers
LinkedList<Integer> list = new LinkedList<>();
int[] arr = new int[5000];
Random random = new Random();
for(int i=0; i<5000; i++){
int rand = random.nextInt(100);
list.add(rand);
arr[i] = rand;
}
Scanner sc = new Scanner(System.in);
System.out.print("Enter element to be search: ");
int key = sc.nextInt();
System.out.println("searching in linked list: ");
long start = System.nanoTime();
int index = linearSearch(list, key);
long end = System.nanoTime();
System.out.println("Time taken to search "+key+" in linked list: "+(end-start)+" nano seconds");
System.out.println("searching in sorted array: ");
start = System.nanoTime();
index = binarySearch(arr, key);
end = System.nanoTime();
System.out.println("Time taken to search "+key+" in sorted array: "+(end-start)+" nano seconds");
}
}
/*
We can apply binary search on Sorted Array.
Time complexity for binary search: O(logn)
Time complexity for linear search: O(n)
Sample run:
Enter element to be search: 45
searching in linked list:
Time taken to search 45 in linked list: 366074 nano seconds
searching in sorted array:
Time taken to search 45 in sorted array: 7343 nano seconds
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.