Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why binarySearch needs a sorted array?

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?

like image 800
aurelius Avatar asked Dec 16 '14 19:12

aurelius


People also ask

Why does a binary search need a sorted array?

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.

Do binary searches have to be sorted?

Binary search works only on a sorted set of elements. To use binary search on a collection, the collection must first be sorted. When binary search is used to perform operations on a sorted set, the number of iterations can always be reduced on the basis of the value that is being searched.

Why is binary search not used on unsorted arrays?

Now, the question arises, is Binary Search applicable on unsorted arrays? So, the answer is NO, it is not possible to use or implement Binary Search on unsorted arrays or lists, because, the repeated targeting of the mid element of one half depends on the sorted order of data structure.

Can binary search be done in unsorted array?

No, binary search needs a sorted array. You might have other properties of an array that enables you to make a search that is more efficient than a mere iteration but the very nature of binary search necessitates sorted data.


2 Answers

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.

like image 194
Lawrence Aiello Avatar answered Oct 26 '22 07:10

Lawrence Aiello


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.

like image 21
Shreeraj Avatar answered Oct 26 '22 07:10

Shreeraj