Menu
Quoting from the docs it says that java.util.Collections.binarySearch(List<? extends Comparable<? super T>> list, T key) returns...
the index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size() if all elements in the list are less than the specified key...
My question is, what significance (if any) does the theorem (-(insertion point) - 1) have such that it's the return value when a key isn't found? Why not just return insertion point for instance?
454
Collections. binarySearch(). This method requires two parameters i.e. the list in which binary search is to be performed and the element that is to be searched. It returns the index of the element if it is in the list and returns -1 if it is not in the list.
The binarySearch() is an inbuilt method of Java Collections class which returns the position of the object in a sorted list.
binarySearch() method is a java. util. Collections class method that returns position of an object in a sorted list. // Returns index of key in sorted list sorted in // ascending order public static int binarySearch(List slist, T key) // Returns index of key in sorted list sorted in // order defined by Comparator c.
The Collections class Java Collections class consists exclusively of static methods that operate on or return collections. It contains polymorphic algorithms that operate on collections, “wrappers”, which return a new collection backed by a specified collection, and a few other odds and ends.
First thing, if the element is not found, a negative value must be returned according to the documetation, or you cannot distinguish between found and not found.
Ok, so why not just -insertion point? Imagine if the insertion point is 0 (the searched element is smaller than all existing ones), then that logic would break - not found would return a non-negative number. Hence the extra -1.
Ok, so why not just -1 always?
Because knowing the insertion point of a non-match in a sorted list is useful to find answers to questions such as:
What is the next element that is bigger than the one I ask for?
and
How many elements are larger than the one I (didn't) find?
And, the way binary search works, the algorithm knows this index when it terminates, so why not share it when it costs nothing extra?
200
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
