Menu
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)?
809
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.
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 .
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.
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.
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.
174
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.
27
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
