java - 查找 Java 中内置搜索的迭代/计数器

Question

我正在创建一个程序，该程序执行二进制和顺序操作并绘制每个搜索的迭代。但是我尝试使用内置的 java 搜索 Collections.binarySearch(list,index) 返回值是我正在搜索的值的索引/位置。我是否可以将返回值设置为计数器/迭代？

for(int i =0; i < 30; i++){
     //java built in search
    Integer retVal3 = Collections.binarySearch(list,n[i]);
    val3.add(retVal3);
}

Answer 1

你基本上有两个选择:

1. 推出您自己的二分搜索方法并在其中添加您的计数/日志记录。
2. 使用自定义比较器对比较操作进行计数。

选项 1 只需复制 Collections.binarySearch() 的源代码即可完成。

选项 2 可以使用如下比较器:

class CountingComparator<T> implements Comparator<T> {
  private final Comparator<T> delegate;
  private int counter;

  public CountingComparator( Comparator<T> delegate ) {
    this.delegate = delegate;
  }

  @Override
  public int compare( T left, T right ) {
    counter++;
    return delegate.compare( left, right );
  }    

  public int getCounter() {
    return counter;
  }
}

然后你像这样使用它:

//since you're searching integers the actual comparator will use the natural order of the elements
CountingComparator<Integer> comp = new CountingComparator<Integer>(Comparator.naturalOrder());    
int index = Collections.binarySearch(list, key, comp);    
int iterationCount = comp.getCounter();

请注意，每次调用 binarySearch() 时都需要该比较器的新实例。