如何在字符串数组上进行多重匹配二进制排序？

I'm attempting to create a Binary Search with multiple matches on a String array. I've tried multiple different approaches and I can't seem to get it to work.

我正在尝试在String数组上创建具有多个匹配项的二进制搜索。我尝试了多种不同的方法,但似乎无法让它发挥作用。

My current code is this:

我目前的代码是这样的:

 public static void searchSinger(Music2[] r, String toFind) {
        int high = r.length;
        int low = -1;
        int probe;
        while (high - low > 1) {
            probe = (high + low) / 2;
            if (r[probe].getSinger().compareTo(toFind) > 0) high = probe;
            else {
                low = probe;
                if (r[probe].getSinger().compareTo(toFind) == 0) {
                    break;
                }
            }
        }
        if ((low >= 0) && (r[low].getSinger().compareTo(toFind) == 0)) {
            linearPrint(r, low, toFind);
        } else System.out.println("Not found: " + toFind);
    }


    public static void linearPrint(Music2[] r, int low,
    String toFind) {
        int i;
        int start = -1;
        int end = -1;

        // find starting point of matches
        i = low - 1;
        while ((i >= 0) && (r[i].getSinger().compareTo(toFind) == 0)) {
            start = i;
            i--;
        }
        // find ending point of matches
        i = low + 1;
        while ((i < r.length) && (r[i].getSinger().compareTo(toFind) == 0)) {
            end = i;
            i++;
        }
        // now print out the matches
        for (i = start; i <= end; i++)
        System.out.println(r[i]);
    }

And if I call the code such as

如果我调用代码如

searchSinger(myLibrary, "Eminem");

and Eminem does exist in myLibrary, it will return

而Eminem确实存在于myLibrary中,它会返回

"Not found: Eminem"

So my question is, what am I doing wrong here? I'm really trying to get this to work, but I can't seem to debug it myself.

所以我的问题是,我在这里做错了什么?我真的想让它工作,但我似乎无法自己调试。

EDIT: Here is the sorting algorithm I'm using:

编辑:这是我正在使用的排序算法:

public static void selectionSort(Music2[] list) {
    int i;
    int k;
    int posmax;
    Music2 temp;
        for (i = list.length - 1; i >= 0; i--) {
            // find largest element in the i elements
            posmax = 0;
            for (k = 0; k <= i; k++) {
                if (list[k].getYear() > list[posmax].getYear()) posmax = k;
            }
            // swap the largest with the position i
            // now the item is in its proper location
            temp = list[i];
            list[i] = list[posmax];
            list[posmax] = temp;
        }
    }

1 个解决方案

#1

It looks like you sort it by year ... and then search by singer. It does not work like this.

看起来你按年份排序......然后由歌手搜索。它不像这样工作。

Imagine a phone book. It is sorted by last name, right? Does it help to search for all people whose phone ends with 7? Of course not ... But if you wanted to look up all Simths, that would be easy, you could do binary search.

想象一下电话簿。它按姓氏排序,对吧?搜索手机以7结尾的所有人都有帮助吗?当然不是......但是如果你想查找所有Simths,这很容易,你可以做二分搜索。

For the binary sort to work, your array needs to be sorted by the same ordering you use when searching. In short, if you are searching for singer, it needs to be sorted by singer.

要使二进制排序起作用,您的数组需要按搜索时使用的相同顺序排序。简而言之,如果您正在寻找歌手,则需要按歌手排序。

#1