Binary search is very efficient, running in log (N) times, compared to linear se
ID: 670669 • Letter: B
Question
Binary search is very efficient, running in log (N) times, compared to linear search which is linear. On the other hand, binary search requires the elements to be presorted. How much time does it take to sort the elements? Both algorithms in the book, namely bubble sort and selection sort, yield square (N), or N*N, performance. In other words, one has to sort the elements in square(N) time and then search in Log (N) time. If we use linear search, it would have just taken N time. So, does it even make sense to have binary search?
Explanation / Answer
Oh. Thats a good one. The difference between linear search and binary search is like, you started searching for some book in a library(Well organized) and in a road side shop which holds a pile of books(unorganized).
Coming to the exact terminology, the linear search will take a time of O(n), and the binary search will take a time of O(log n). Binary search is better as of now. But it needs a sorted list to start with. To sort a list even a best case algorithm will take O(n log n) time, there fore, sorting + searching(binary search) will take O(n log n) time more when compared to linear search O(n).
This holds true when you are searching for an element only once.
Let us consider another scenario, you want to search for an element(different one everytime) for n times.
So, if a linear search requires O(n) time to search, for a total of n searches it requires n* O(n) = n2 comparisions.
If you sort the list with best efficient algorithm. The time it requires is: O(n log n), and then applying a binary search requires O(log n) time. For searching n elements it requires: O(n log n) (for sorting) + O(log n) (for searching once) * n.
= n * O(log n) which is again n * log n comparisions which is much better than n2 comparisions.
Hence, if you want to search only once, its ok to go with a linear search, but when you want to search multiple number of times, keep in mind that you need not sort everytime, and a single sort will make the subsequent searches much faster and efficient.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.