Time complexity of binary search for an unsorted array

arrays sorting binary-search
user1521306 picture user1521306 · Apr 9, 2013 · Viewed 40.7k times · Source

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?

Answer

LuiNova picture LuiNova · Apr 9, 2013

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)

Related questions

Sort array of objects by string property value

I have an array of JavaScript objects: var objs = [ { first_nom: 'Lazslo', last_nom: 'Jamf' }, { first_nom: 'Pig', last_nom: 'Bodine' }, { first_nom: 'Pirate', last_nom: 'Prentice' } ]; How can I sort them by the value of last_nom in JavaScript? …

Read More
Sorting an array of objects by property values

I've got the following objects using AJAX and stored them in an array: var homes = [ { "h_id": "3", "city": "Dallas", "state": "TX", "zip": "75201", "price": "162500" }, { "h_id": "4", "city": "Bevery Hills", "state": "CA", "zip": "90210", "price": "319250" }, { "h_id": "5", "city": "New York", "state": "NY", "zip": "00010", "…

Read More
How to Sort Multi-dimensional Array by Value?

How can I sort this array by the value of the "order" key? Even though the values are currently sequential, they will not always be. Array ( [0] => Array ( [hashtag] => a7e87329b5eab8578f4f1098a152d6f4 [title] =&…

Read More