PHP 7 Data Structures and Algorithms

Searching an unsorted array - should we sort first?

So now, we are in a situation where we have an array with n items and they are not sorted. Since we know binary search is faster, we have decided to sort it first and then search for the item using a binary search. If we do so, we have to remember that the best sorting algorithms have a worst time complexity of O(nlog n), and for binary search, the worst case complexity is O(log n). So, if we sort and then apply the binary search, the complexity will be O(n log n) as it is the biggest one compared to O(log n). However, we also know that for any linear or sequential search (sorted or unsorted), the worst time complexity is O(n), which is much better than O(n log n). Based on the complexity ...