Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Java Arrays binarySearch() insertion point

As per Java doc for Arrays.binarySearch(int[] a, int 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.

I need to understand why its returning (-(insertion point) - 1), why not just -(insertion point)?

like image 809
Vasu Avatar asked Aug 06 '16 16:08

Vasu


People also ask

How does arrays binarySearch work in Java?

binarySearch() method: (It) Searches the specified array of bytes for the specified value using the binary search algorithm. The array must be sorted (as by the sort(byte[]) method) prior to making this call. If it is not sorted, the results are undefined.

What arrays return binarySearch?

Returns. The index of the specified value in the specified array , if value is found; otherwise, a negative number. If value is not found and value is less than one or more elements in array , the negative number returned is the bitwise complement of the index of the first element that is larger than value .

How do you find the insertion point in binary search?

Approach to implement Binary Insertion sort:Iterate the array from the second element to the last element. Store the current element A[i] in a variable key. Find the position of the element just greater than A[i] in the subarray from A[0] to A[i-1] using binary search. Say this element is at index pos.

What is binarySearch in Java?

Binary Search in Java is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. It works only on a sorted set of elements. To use binary search on a collection, the collection must first be sorted.


2 Answers

Because if it returned -(insertion point), and the insertion point was 0, then you would not be able to distinguish between I found it, it's at index 0, and I haven't found it, you can insert at index 0.

like image 174
JB Nizet Avatar answered Sep 19 '22 12:09

JB Nizet


Consider an array:

int intArr[] = {5,12,20,30,55};

now consider these two binary search statements:

System.out.println("The index of element 5 is : " + Arrays.binarySearch(intArr,5));

and

System.out.println("The index of element 4 is : " + Arrays.binarySearch(intArr,4));

Output

The index of element 5 is : 0
The index of element 4 is : -1

because of that -1, we can differentiate between the two outputs. If there was no -1 then both of these statements would have given the same output, i.e., 0.

like image 27
Raman Sahasi Avatar answered Sep 19 '22 12:09

Raman Sahasi