Collections.binarySearch 是如何运作的？

Question

我想了解 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);


   }    
}

这段代码的输出是-1。

当元素按此顺序插入后

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

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

Answer 1

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

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.

如果数据确实已排序，该方法将 return 查找元素的索引（如果找到），否则 (-(insertion point) - 1)，如 the documentation.[=15 中指定=]

示例：

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

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

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

Answer 2

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

正如@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 = -0 - 1

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

Answer 3

■ 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)

Answer 4

这是 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;
            }
        }
    }
    
}

Collections.binarySearch 是如何运作的？

How does Collections.binarySearch work?

java

collections