Question

If you run the binary search method on a set of unordered data, What happens? Why? How you would correct this issue?

Answer 1

If we run the binary search method on a set of unordered data then the results are unpredicable. If the data set has the target, it may or may not be found.

Just for kicks, I ran a little experiment. First, I picked an array size and generated an int array {0, 1, ..., size-1}. Then I shuffled the array, did a binary search for each value 0, 1, ..., size-1 and counted how many of these were found. For each size, I repeated the shuffle/search-for-each-value steps 100,000 times and recorded the percent of searches that succeeded. (This would be 100% for a sorted array.) The results are (rounded to the nearest percent):

Size    % Hit
 10      34%
 20      22%
 30      16%
 40      13%
 50      11%
 60      10%
 70       9%
 80       8%
 90       7%
100       6%

So the larger the array, the worse the effects of not sorting. Even for relatively small arrays, the results are pretty drastic.

Binary Search relies on data being sorted. It picks an element in an array and determines 1. If this is the element it is searching 2. If it is not the element it is looking for, where can it possibly find the element.

The second point relies on data being sorted to make a decision. Imagine an unsorted data. Just by comparing the search key with the element that we have picked, we will not be able to identify where the element could occur.

So, binary search cannot work consistently in unsorted data.

We would correect this issue by first sorting the input data and then applying the binary search on it.