链表中字符串的二进制搜索

Question

我需要对具有各种数据类型的链表执行二进制搜索。下面的代码将无法编译。我似乎无法让 compareTo() 工作。

这里是链表class:

public class Contributor {

private String firstName;
private String lastName;
private String country;
private String phone;
private double contribution;
private int id;}

二分查找法如下。搜索需要使用二分法查找某个lastName。

 public void binarySearch(List<Contributor> l, String key) {
    System.out.println("Binary search.");

    int upperBound = l.size();
    int lowerBound = 1;
    int midpoint = (upperBound + lowerBound) / 2;
    int difference = upperBound - lowerBound;

    for (int i = 0; i < l.size(); i++) {
        if (key.compareTo(l.get(midpoint - 1))&& difference != 1) {
            upperBound = midpoint - 1;
            midpoint = upperBound / 2;
        } else if (key.compareTo(l.get(midpoint - 1)) && difference != 1) {
            lowerBound = midpoint + 1;
            midpoint = (lowerBound + upperBound) / 2;

        } else if (key.equals(l.get(midpoint - 1))) {
            midpoint = midpoint - 1;

            System.out.println("We found " + key + " at position " + midpoint + " in the list.");
            i = l.size();
        } else {
            System.out.println("We couldn't find " + key + " in the list.");
            i = l.size();
        }
    }
}

Answer 1

通过查看您的代码 l.get(midpoint-1) returns 贡献者对象不是字符串，并且 key.compareTo 方法只能接受字符串类型的参数。

Answer 2

compareTo() 函数 returns 整数值。所以试试

if(key.compareTo(str) < 0)

或

if(key.compareTo(str) > 0)

或

if(key.compareTo(str) == 0)

还将它与来自贡献者 class 的字符串进行比较，而不是与 class 本身进行比较。即

if(key.compareTo((l.get(midpoint - 1)).firstName)<0)

另一个逻辑错误是当你这样做的时候

midpoint = upperBound / 2;

您假设 lowerbound 为 1。但它的值可能会在迭代中发生变化。所以也考虑一下

Answer 3

这里有一个逻辑错误 - 正如 Akshay 所说，你的密钥是 String，所以在 Contibutor 的列表中搜索它没有意义 - 你需要搜索 Contributor.

除此之外，二进制搜索的前提是列表已排序，这要求您的 Contributor 对象是 Comparable（或者至少您提供 Comparator.

我修改了您的代码以解决这些问题：

class Contributor implements Comparable<Contributor>{

    private String firstName;
    private String lastName;
    private String country;
    private String phone;
    private double contribution;
    private int id;

    public int compareTo(Contributor o) {
        return Integer.valueOf(id).compareTo(o.id);
    }
}

public class BinarySearch {
    /**
     * Performs a binary search for <code>key</code> in the list <code>l</code>.
     * 
     * @param l Ordered list of Contributors.
     * @param key Value to search for.
     */
    public void binarySearch(List<Contributor> l, Contributor key) {
        System.out.println("Binary search.");

        int upperBound = l.size();
        int lowerBound = 1;
        int midpoint = (upperBound + lowerBound) / 2;
        int difference = upperBound - lowerBound;

        for (int i = 0; i < l.size(); i++) {
            if (key.compareTo(l.get(midpoint - 1)) <0 ) {
                upperBound = midpoint - 1;
                midpoint = upperBound / 2;
            } else if (key.compareTo(l.get(midpoint - 1))>0 ) {
                lowerBound = midpoint + 1;
                midpoint = (lowerBound + upperBound) / 2;

            } else if (key.equals(l.get(midpoint - 1))) {
                midpoint = midpoint - 1;

                System.out.println("We found " + key + " at position "
                        + midpoint + " in the list.");
                i = l.size();
            } else {
                System.out.println("We couldn't find " + key + " in the list.");
                i = l.size();
            }
        }
    }
}

这应该可以修复您的编译错误，尽管正如其他人指出的那样，搜索逻辑本身存在一些错误。另请注意，binarySearch 方法的先决条件是对列表进行排序，并且应记录此要求。我已经添加了一个 javadoc 注释来解释这一点。

链表中字符串的二进制搜索

Binary Search of String within a linked list

java

search

binary