Incorrect value in vector when binary search

Question

import java.util.Arrays;

/**
 * @author Vinicius
 *
 */
public class Vetor04 {
    /**
     * @param args
     */
    public static void main(String[] args) {
        int vet[] = {3, 7, 6, 1, 9, 4, 5};
        int s = Arrays.binarySearch(vet, 3);
        System.out.println(s);

    }

}

I’m trying to do vector index 3 vet appear but instead of printing 1 print -5, what is the reason for this?

Answer 1

Although you want to use the method Arrays.binarySearch() to find a value in a array not classified (the correct term, because ordered the array is, it has an order, data entry order) and this method should not be applied. It was created to handle when you have already sorted data.

The solution of classifying the array to then make the binary search work, but it’s not right:

It is only worth using a binary search with a collection of data that is guaranteed to be classified since the sorting effort is at least (and would be in an ideal condition that in practice does not happen) equal to doing a linear search, it is usually much higher. And in practice the classification algorithm is less efficient even in detail than the linear search in most situations because it is bad of reference location. To be more accurate the linear search arrive be better even in arrays small that are already classified.

So if you want to learn to apply the algorithm correctly, you shouldn’t apply it in this case. You’re learning to use the mechanism, but you’re also learning to use it the wrong way and it can haunt you forever. And we’re not talking about a small difference when the volumes are bigger, you can create very tragic situations if you keep doing so because you learned that solves in Stack Overflow.

Doing linear search produces the same result much more efficiently. Although you don’t need this efficiency in an exercise the goal is not even this, is to teach right to apply well in the next times:

class Main {
    public static void main (String[] args) {
        int vet[] = { 3, 7, 6, 1, 9, 4, 5 };
        for (int i = 0; i < vet.length; i++) if (vet[i] == 3) {System.out.println(i); break; }
    }
}

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

There are several other ways to do this.

And note that it returns the real position, you may want it or not. The ready function returns the insertion position.

The worst case of this algorithm is O(N), but it may be O(1) in the best case. The best case of the binary search that needs to classify the data is O(N)+O(1), but in practice this does not happen and most cases will be O(Nlogn)+O(1) and may even be O(N2)+O(1). In large volumes can go from seconds to hours.

Not to mention, you don’t run the risk of array not be classified and go wrong, as happened. And the only way to ensure in a larger code is:

• sort every time you do binary search (very inefficient)
• use a structure that you ensure has been sorted at first and is no longer changed
• use a structure that automatically classifies itself every time it is changed.

It may not be what the AP wants, but it’s important for other people to know the right way to do this kind of thing and not learn wrong. Note that this is wrong even in this case proposed in the question, even if it works, unless the question is written, the performance does not matter and typing less characters matters.

Read the comments below for important extra information.

Answer 2

As I reported in the commentary, binary research has the principle of ascending ordering, and its array is not so ordered from the least to the highest value. Sort with Arrays.sort that the value location is returned, example:

int vet[] = {3, 7, 6, 1, 9, 4, 5};
Arrays.sort(vet); // ordenação
int s = Arrays.binarySearch(vet, 3);
System.out.println(s);

Online Example

'Cause the weird numbers, according to Kathy Sierra’s book page 322, Successful searches return the index of the element being searched and Unsuccessful searches return an int index representing the insertion point.

I exemplified about the code of the question, we can not imagine another way if the question is described so, clear (programming is limitless) that can be done otherwise. The reasons often that led to this questioning is the explanation of the previous text, namely the lack of knowledge about what it is doing.

Remember that here on the site has an almost equal answer Difficulties with binarySearch Class Arrays method and the same solution was cited.

Of course, it could have used other forms of research, such as Linear, but, I always go by the question.