Why binarySearch needs a sorted array?

Question

If binarySearch method requires you to sort your array before passing it as parameter to the method call, why not do a sort in the binarySearch method?

Gibberish

Because the sort takes more time than the search, that's why. You only have to do the sort once, and then binary search the resulting data set multiple times. – Gregorygregrory

The point of the search is not to generate a sorted array. It is to locate a specific value. The search requires a sorted array. How would you do a binary search on an unsorted array? – Dotation

This is the pre-condition that requires a binary search. If I call binary search on the same array multiple times, I would not expect to sort it each time because that would gives you poor performance. If you need to sort the array to perform a binary search, then just do a linear search. That will be faster. – Scalise

Because it's a search algorithm, not a sort algorithm. – Lack

You probably need to provide a bit of code. It's unclear what you define as "in the binarySearch" method means. Within the method, before you search, you can definitely sort it. – Foyer

Robert Harvey - this is the right answer - add your comment as answer to close it :) – Gibberish

@RobertHarvey In this case your comment should be an answer. – Lakeesha

Answer 1

Binary search works by assuming the middle of the array contains the median value in the array. If it is not sorted, this assumption does not make sense, since the median can be anywhere and cutting the array in half could mean that you cut off the number you were searching for.

The reason binary search does not do the sort itself is because it does not need to...the array is already sorted.

Amosamount

The question is not why the array must be sorted, but why the binarySearch method doesn't do the sorting itself. – Predigestion

If he understood how binary search worked, he would know the answer to that question. That's why I explained it. – Amosamount

Answer 2

It is generally considered good programming practice to define functions that focus on one goal. This leads to more modular, reusable code and avoids code repitition.

For example, it would be advisable to implement a function that does the sorting for you and which you can then simply call in different search functions. This way, you do not have to repeat the sorting code in every search function you want to implement.

Falkner

This is not the reason binary search shouldn't do the sorting. The sort is slower than just reading all items to find out where they should go – Lakeesha

Sorting is O(N log N). Linear search is O(N) average time, looking at all elements up to the key. Binary search is O(log N) - it doesn't have time to look at every element once, let alone enough times to sort them. Doing so would defeat the purpose of having a binary search function. – Chela