CPT307 Week 2 Discussion

The two different types of searching algorithms are linear and binary. An algorithm is a series of events that are taken to accomplish a task (Lysecky, Vahid, Lysecky, & Givargis, 2015). A linear search algorithm searches a list of values consecutively from the beginning to end. One downfall to this algorithm is the runtime. Runtime is the time the algorithm takes to execute” (Lysecky et al., 2015, sect. 1.1). If your array has a large amount of values, it will have a longer runtime than an array with only few elements. For example, if you are doing a linear search for names in an employee database will search for the name by starting at the beginning and iterating through each name until it finds the correct one. 

A binary search has a faster runtime when compared to a linear search. In order to do a binary search, the elements must be sorted. Using the same example of searching through an employee database, the names would first have to be sorted alphabetically. A binary search will split the list in half and see whether the name came before or after that point. It continues this process until the element is found. 

To along with searching through elements, you can sort these elements. According to Shaffer (2013), there are three sorting algorithms, selection, insertion, and bubble. A selection sort works by selecting the smallest value and putting it first and continuing this process until all values are in the correct order. An insertion sort “iterates through a list of records” (Schaffer, 2013, p. 225). Insertion sorts takes values and inserts them into the correct position until all values all sorted. A bubble sorts iterates through all the values and pushes lower values to the top. When it comes to runtime this sorting algorithm is the slowest.

Another factor in which type of algorithm is used is the time and space complexity. Time complexity is determined on the size of the information, which will determine how many steps are needed to complete the task while space complexity is how much storage is needed for the size of the values (Sorting, searching, and algorithm analysis, 2014). For the average person, the space and time complexity would not matter. Regardless of which algorithm you execute, the average person would not be able to decipher if one algorithm was milliseconds, nanoseconds, etc. faster then another algorithm. I believe when it comes to a supercomputer, it does matter which algorithm is faster. With supercomputers, you want them to complete their tasks as quickly as possible, so milliseconds and nanoseconds would definitely matter. 

References

Lysecky, R., Vahid, F., Lysecky, S., & Givargis, T. (2015). Data structures essentials. Retrieved from https://zybooks.zyante.com/#/zybook/DataStructuresEssentials

Shaffer, C. A. (2013). Data structures and algorithm analysis (3.2 ed.). Retrieved from http://people.cs.vt.edu/~shaffer/Book/JAVA3elatest.pdf

Sorting, searching and algorithm analysis. (2014). Retrieved from http://python-textbok.readthedocs.io/en/latest/Sorting_and_Searching_Algorithms.html

Binary Search

public class BinarySearchDemo {
boolean binarySearch(int[] array, int value) {
boolean flag = false;
int low = 0;
int high = array.length - 1;
int mid = (low + high) / 2;
while (low <= high) {
if (array[mid] < value) {
low = mid + 1;
} else if (array[mid] > value) {
high = mid - 1;
} else {
flag = true;
break;
}
mid = (low + high) / 2;
}
return flag;
}
public static void main(String[] args) {
int[] array = {5,10,15,20,25,30,35,40,45,50,55,60,65,70};
int search = 17;
if (binarySearch(array, search) == true) {
System.out.println("The number " + search + " exists in the array.");
} else {
System.out.println("The number " + search + " does not exist in the array.");
}
search = 45;
if (binarySearch(array, search) == true) {
System.out.println("The number " + search + " exists in the array.");
} else {
System.out.println("The number " + search + " does not exist in the array.");
}
}
}