How to obtain a sorted array for binary search operation?

I have recently learnt the binary search.... I am very much impressed by its time complexity of O(log n), but I am having a doubt that for obtaining sorted array i must have to apply sorted operation i.e. minimum O(nlogn) complexity which is quite more.


If you have a list that it not sorted (or not guaranteed to be sorted), linear search is the way to go. Linear search is O(n) while sorting it is O(nlog n), which is worse. Even checking if a list is sorted is O(n).

In the case that you want to search the list only once, you are better of with linear search. If you're going to search several times you may benefit from sorting the list first. In order to find out what is best for your specific case, you will have to analyze the problem.

The idea is that you sort the list one time, and keep the result. Subsequent searches are O(log n). So your complexity across many searches is (n log n) + S*log(n), where S is the number of searches you'll make. If you don't sort the array, then your multiple searches cost O(S*n).


 ? Does initialising an auxiliary array to 0 count as n time complexity already?
 ? Why is code like i=i*2 considered O(logN) when in a loop?
 ? How do I count primitive operations in this algorithm?
 ? Find two numbers from BST which sum to given number K
 ? Two unsorted single linked list to one sorted single linked list
 ? Find two points in a given set of points in 2D plane with least distance in less than O(n^2) time
 ? When analyzing complexity - is the base of the logarithm significant?
 ? Algorithm review for time complexity
 ? Big O(h) vs. Big O(logn) in trees
 ? Any built-in Matlab function to find if a certain number lies between two members of a vector?