Linear Search VS Binary Search | Sololearn: Learn to code for FREE!

+13

# Linear Search VS Binary Search

For those who are new to these terms: Linear search looks down a list, one item at a time. E.g. assuming we have an array of size 1000 which contains unsorted, unique numbers, and we want to find a specific key within the entire array: for (int i = 0; i < 1000; i++) { if (array[i] == 39) { std::cout << "Found."; break; } } Binary search on the other hand starts in the middle of the entire list. If the data stored is smaller than provided key, the program will continue to search on the right side of the list. Conversely, if the data stored is larger than the provided key, the program will continue searching on the left aide of the list. This operation continues until the data matches the key provided. Binary search requires data to be sorted. E.g. 1, 4, 5, 10, 15, 20, 40, 41, 45, 50, 60, 61, 71 Assuming the key provided is 20. The program would usually take the median of the set/list to begin with binary search. In this case, we start with 40. 40 > 20, hence the program continues searching on the left side. The median between 1 and 40 is 10. Taking 10 < 20, the program continues to search on the right side. Program takes on of the nearest element to the median between 10 to 40 and lands on 20. 20 == 20, the search is complete. ************************************ Now, is linear search necessarily slower than binary search? It is generally agreeable to a certain extent. However, binary search requires sorting algorithms to keep the list sorted prior to it's execution. What is your opinion on linear search VS binary search, in terms of efficiency? When should we prefer one over another?

5/23/2017 4:07:32 AM

Hatsy Rei