java - 如何使用二分查找获得更多的搜索数据？

Question

首先，我为我的英语表示歉意，这是我第一次在 stackoverflow 上提问，所以如果我错过了什么，请指出。

所以我是java新手，并在 friend 的帮助下尝试二分搜索。该代码用于通过产品ID搜索后显示产品信息。我设法让它返回找到 Id 的索引号，但问题是当我输入多个相同的 ID 时，它只显示 1 个数据。我希望我的程序显示找到 ID-12 的所有索引。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class MyListBinarySearch {

public static void main(String a[]){

    List<Emp> empList = new ArrayList<Emp>();
    empList.add(new Emp(12,"Apple,50,10-5-2014"));
    empList.add(new Emp(12,"Apple,50,5-5-2014"));
    empList.add(new Emp(124,"Apple,50,2-5-2014"));
    empList.add(new Emp(302,"Apple,50,2-5-2014"));
    empList.add(new Emp(12,"Apple,50,2-5-2014"));

    Emp searchKey = new Emp(12,"String");
    int index = Collections.binarySearch(empList, searchKey, new EmpComp());
    System.out.println("Index of the searched key: "+index);
}
}

class EmpComp implements Comparator<Emp>{

public int compare(Emp e1, Emp e2) {
    if(e1.getEmpId() == e2.getEmpId()){
        return 0;
    } else {
        return -1;
    }
}
}

class Emp {

private int empId;
private String empInfo;


public Emp(int id, String info){
    this.empId = id;
    this.empInfo = info;

}

public int getEmpId() {
    return empId;
}

public void setEmpId(int empId) {
    this.empId = empId;
}

public String getEmpInfo() {
    return empInfo;
}

public void setEmpInfo(String empInfo) {
    this.empInfo = empInfo;
}

@Override
public String toString(){
    return empId+" : "+empInfo;
}
}

输出是“搜索关键字的索引:2”我想显示找到搜索关键字的所有索引。我怎么做 ？我需要循环吗？

Answer 1

您有两个问题:

1. 当当前元素大于被比较元素时，比较器应返回大于 0 的值；当元素等于时，返回 0；当当前元素小于被比较元素时，比较器应返回小于 0 的值。您当前的实现不涵盖这一点。
2. 二分搜索仅适用于排序数组/列表。您的列表未按 ID 排序。

解决此问题后，您将可以有效地使用二分搜索。检索到元素为 12 的索引后，可以在该元素周围搜索，检索所有具有相同 Id 的元素。

这是一个如何实现它的想法:

int index = Collections.binarySearch(empList, searchKey, new EmpComp());
List<Emp> empsWithId12 = new ArrayList<Emp>();
for (int i = index - 1; i >= 0; i--) {
    Emp emp = empList.get(i);
    if (emp.getId() == 12) {
        empsWithId12.add(emp);
    } else {
        break;
    }
}
Collections.reverse(empsWithId12);
for (int i = index; i < empList.size(); i++) {
    Emp emp = empList.get(i);
    if (emp.getId() == 12) {
        empsWithId12.add(emp);
    } else {
        break;
    }
}

请注意，通过将逻辑移至方法中可以大大改进上述想法。