CODEWITHSUNDEEP
javaarrayssortingbinary-search
roshan
roshan

Reputation: 2510

How Arrays.binarySearch() works without sorting

I am curious to know what is the logic behind the answer I am getting when I am using Arrays.binarySearch without sorting.

int d[]={6,-4,12,0,-10};
int x=12;
int y=Arrays.binarySearch(d,x);

   System.out.println(y);

Output:2

I am preparing for a contest of java in which such rare cases are raised , so i asked this question.Please help with any possible solution.

Upvotes: 0

Views: 4682

Answers (4)

Thirumalai Parthasarathi
Thirumalai Parthasarathi

Reputation: 4671

now the javadocs states that

The array must be sorted (as by the sort(int[]) method) prior to making this call. If it is not sorted, the results are undefined. If the array contains multiple elements with the specified value, there is no guarantee which one will be found.

Upvotes: 0

Stefano Sanfilippo
Stefano Sanfilippo

Reputation: 33046

You could get anything. Reading the javadocs for Arrays.binarySearch

The array must be sorted (as by the sort(int[]) method) prior to making this call. If it is not sorted, the results are undefined.

Upvotes: 0

Johannes H.
Johannes H.

Reputation: 6167

According to the Java API reference, if it is not sorted, the results are undefined.

In your case, you got lucky: binary search is "divide and conquer".
The algorithm looks at the middle of the array. If it is the number, it returns (was the case in your example - that's why it worked).
If the element is bigger than the one you search for, repeat with the left part (the ones with the lower nubmers). Otherwise use the right one.
Repeat until you found the element. If you have only 1 element left, and it's not the element you searched for, the element is not in that array. In case of the Java implementation, it just returns the index of the last element that was found (which happens to be i(-(insertion point) - 1))

Upvotes: 3

tskuzzy
tskuzzy

Reputation: 36456

You got lucky. The Java implementation requires the array to be sorted for it to guarantee a correct answer:

The array must be sorted (as by the sort(int[]) method) prior to making this call. If it is not sorted, the results are undefined.

Source

Upvotes: 4

Related Questions