CODEWITHSUNDEEP
java
user1448750
user1448750

Reputation:

Java Arrays.binary search returns wrong data even when array is sorted

The documentation writes that "Arrays.binarySearch return a.length if all elements in the array are less than the specified key." So in the following program, I am expecting the value 4 to be printed but it prints -4. Why this anomalous behaviour?

import java.io.*;
import java.math.*;
import java.util.*;
import java.lang.*;

public class Main{ 
    public static void main(String[] args)throws java.lang.Exception{
        int[] a = new int[3];
        a[0] = 3;
        a[1] = 8;
        a[2] = 9;
        System.out.println(Arrays.binarySearch(a, 15));         
    }
}

Upvotes: 3

Views: 488

Answers (2)

vidit
vidit

Reputation: 6451

Quoting from Java Docs..

Returns: index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1).

where 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

In your example, all elements are less than 15 and length of the array is 3. So the insertion point is 3 and therefore binarySearch returns -3-1 = -4.

Upvotes: 8

Dark Knight
Dark Knight

Reputation: 8347

If it's returning a negative value it's not found:

http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html

public static int binarySearch(Object[] a, Object key)

Returns: 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.

Upvotes: 0

Related Questions