CODEWITHSUNDEEP
arrayssortingbinary-search
user1521306
user1521306

Reputation: 185

Time complexity of binary search for an unsorted array

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?

Upvotes: 14

Views: 55498

Answers (3)

yuvrajm
yuvrajm

Reputation: 318

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.

Upvotes: 4

Akash saha
Akash saha

Reputation: 1

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.

Upvotes: 0

LuiNova
LuiNova

Reputation: 396

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)

Upvotes: 34

Related Questions