java Collections.binarySearch 是如何工作的？

How does Collections.binarySearch work?

提问by Kabachok

I am trying to understand how Collections.binarySearch work in Java. I don't quite understand the output I get.

我想了解 Collections.binarySearch 在 Java 中是如何工作的。我不太明白我得到的输出。

public static void main(String args[]) {
      // create arraylist       
      ArrayList<String>  arlst=new ArrayList<String> ();


      arlst.add("A");
      arlst.add("D");
      arlst.add("C");
      arlst.add("B");
      arlst.add("E");

      int index=Collections.binarySearch(arlst, "D", Collections.reverseOrder());     

      System.out.println(index);


   }    
}

The output of this code is -1.

此代码的输出为 -1。

And when the elements have been inserted at this order

当元素已按此顺序插入时

      arlst.add("D");
      arlst.add("E");
      arlst.add("C");
      arlst.add("B");
      arlst.add("A");

I get 0 as a result. I thought the negative number was a result if the element was not found. Could anybody please clarify the output I receive?

结果我得到0。如果未找到元素，我认为负数是结果。有人可以澄清我收到的输出吗？

回答by aioobe

Your data must be sorted according to the given comparator for the binary search to work as intended. (If it's not, the behavior is undefined.)

您的数据必须根据给定的比较器进行排序，二进制搜索才能按预期工作。（如果不是，则行为未定义。）

The list must be sorted into ascending order according to the specified comparator (as by the sort(List, Comparator)method), prior to making this call.

sort(List, Comparator)在进行此调用之前，必须根据指定的比较器（如方法）将列表按升序排序。

If the data is indeed sorted, the method will return the index of the sought element (if it's found) otherwise (-(insertion point) - 1), as specified in the documentation.

如果数据确实已排序，则该方法将返回所查找元素的索引（如果找到），否则(-(insertion point) - 1)，如文档中所述。

Example:

例子：

// Make sure it's sorted
Collections.sort(arlst, Collections.reverseOrder());

int index=Collections.binarySearch(arlst, "D", Collections.reverseOrder());     

System.out.println(index);  // prints 1

回答by JW.ZG

Just to make it clearer - why the output is -1. Yes, you didn't sort it first is a big mistake. But here are some other things to take clear as well.

只是为了更清楚 - 为什么输出是-1。是的，您没有先对其进行排序是一个很大的错误。但这里还有一些其他的事情需要弄清楚。

As @aioobe mentioned in his answer, but he didn't make it clear enough though I think. What does (-(insertion point) - 1)mean? Here is what the doc says.

正如@aioobe 在他的回答中提到的，但我认为他没有说得足够清楚。什么(-(insertion point) - 1)意思？这是医生所说的。

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. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

搜索键的索引，如果它包含在列表中；否则，(-(插入点) - 1)。插入点定义为将键插入列表的点：大于键的第一个元素的索引，如果列表中的所有元素都小于指定的键，则为list.size()。请注意，这保证当且仅当找到键时返回值将 >= 0。

So to make the answer more clear: -1 = -0 - 1

所以为了让答案更清楚： -1 = -0 - 1

What I want to underline here is that the output maybe -2or -3or whatever. Because if all elements in the list are less than the specified key, the output will be -list.size() - 1.

我想在这里强调的是，输出可能-2或-3或其他。因为如果列表中的所有元素都小于指定的键，则输出将为-list.size() - 1.

回答by Priyanka

■ Searches are performed using the binarySearch() method.
■ Successful searches return the int index of the element being searched.
■ Unsuccessful searches return an int index that represents the insertion point. The insertion point is the place in the collection/array where the element would be inserted to keep the collection/array properly sorted.
        * Return values and 0 indicate successful searches
        * Negative numbers to indicate insertion points
        * The first available insertion point is -1. Therefore,the  actual insertion point is represented as (-(insertion point) -1)

回答by Catalyst0

Here is the inner workings of the binarySearch method:

这是 binarySearch 方法的内部工作原理：

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package binarysearch;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;


public class BinarySearch {

    static ArrayList<String> strings;
    public static void main(String[] args) {
        String sample = "a quick brown fox jumped right over the lazy dog while an active lion was nowhere in sight";
        String[] simpleArray = sample.split(" ");
        strings = new ArrayList(Arrays.asList(simpleArray));
       Collections.sort(strings);
       // Enter a search string; here it is "lazy"
       binarySearch(strings, "lazy");
       System.out.println("");
       // Print the Array contents for convenience
       printArrayList(strings);
    }

    static void printArrayList(ArrayList<String> strings) {
        int i = 0;
        for (String s: strings) {
            i++;
            System.out.println(i + s );
        }
    }



    static void binarySearch (ArrayList<String> strings, String searchString) {
        boolean debug = true;
        int low = 0;
        int high = strings.size();
        int mid = 0;
        while (low <= high) {
            // The > symbol marks the hits before search is concluded
            System.out.print(">");
            mid = (high + low) / 2;

            int comparison = strings.get(mid).compareToIgnoreCase(searchString);
            if (comparison > 0) {
                high = mid - 1;
            } else if (comparison < 0) {
                low = mid + 1;
            } else {
                int temp = mid;
                System.out.println("Found '" + searchString + "' at: " + (temp + 1) );
                break;
            }
        }
    }

}