CODEWITHSUNDEEP
javaarraysbinary-search
Muntaser Abukhadijah
Muntaser Abukhadijah

Reputation: 171

Arrays.binarySearch() returns wrong insertion point

This is the code:

public class Main {

    public static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {

        int arr[] = {10,50,999,1000};
        int index = Arrays.binarySearch(arr,55);
        System.out.println(index);
    }
}

The output here is '-3', if the output from this formula "(-(insertion point) - 1)" that means the insertion point is '4' and that is not right.

So what i am missing?

Upvotes: 1

Views: 490

Answers (2)

Morteza Jalambadani
Morteza Jalambadani

Reputation: 2445

There is no missing.Array.binarySearchs Returned index of the search key, if it is contained in the array; otherwise, (-(insertion point) – 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found. this describtion is from here.

Upvotes: 0

Zabuzard
Zabuzard

Reputation: 25903

The insertion point is 2, not 4.

According to the official documentation:

The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key [...]

Your array with indices is

[10, 50, 999, 1000]
  0   1    2     3

The first element greater than 55 is 999 at index 2. Remember that indices start counting at 0.

So the insertion point is 2. With the formula (-(insertion point) - 1) the return value must thus be:

(-(2) - 1) = -3

Which is exactly what you got.

Upvotes: 2

Related Questions