I am stuck up with two time complexities. To do a binary search with sorted array is O(logN). So to search an unsorted array we have to sort it first so that becomes O(NlogN). So then we can perform binary search which gives the complexity as O(N) but I have read that it could be O(NlogN). Which is correct?
1
-
1It's true, a binary search will not work on an unsorted array; however, you'd first have to sort the array to perform the binary search. At least that's how I have learned recently.user2373448– user23734482017-11-21 21:16:36 +00:00Commented Nov 21, 2017 at 21:16
Add a comment
|
3 Answers
Binary Search is for "Sorted" lists. The complexity is O(logn).
Binary Search does not work for "un-Sorted" lists. For these lists just do a straight search starting from the first element; this gives a complexity of O(n). If you were to sort the array with MergeSort or any other O(nlogn) algorithm then the complexity would be O(nlogn).
O(logn) < O(n) < O(nlogn)
Comments
The answer to your question is in your question itself.
You are first sorting the list. If you sort your list using quick or merge sort, the complexity becomes o(n*log n). Part - 1 gets over.
Second part of performing a binary search is done on the 'Sorted list'. The complexity of binary search is o(log n). Therefore ultimately the complexity of the program remains o(n*log n).
However, if you wish to calculate the median of the array, you don't have to sort the list. A simple application of a linear, or sequential, search can help you with that.
Comments
The time complexity of linear search is O(n) and that of binary search is O(log n) (log base-2). If we have an unsorted array and want to use binary search for this, we have to sort the array first. And here we have to spend a time O(n logn) to sort the array and then spend time to search element.
