Java 如何使用 binarySearch 或其他方法在字符串数组中搜索字符串？

How do I search for a String in an array of Strings using binarySearch or another method?

提问by qodeninja

Using binarySearch never returns the right index

使用 binarySearch 永远不会返回正确的索引

int j = Arrays.binarySearch(keys,key);

where keys is type String[]and key is type String

其中键是类型String[]，键是类型String

I read something about needing to sort the Array, but how do I even do that if that is the case?

我读了一些关于需要对数组进行排序的内容，但如果是这种情况，我该怎么做？

Given all this I really just need to know:

鉴于这一切，我真的只需要知道：

How do you search for a String in an array of Strings (less than 1000) then?

那么如何在字符串数组（小于 1000）中搜索字符串？

采纳答案by TofuBeer

From Wikipedia:

来自维基百科：

"In computer science, a binary search is an algorithm for locating the position of an element in a sorted list by checking the middle, eliminating half of the list from consideration, and then performing the search on the remaining half.[1][2] If the middle element is equal to the sought value, then the position has been found; otherwise, the upper half or lower half is chosen for search based on whether the element is greater than or less than the middle element."

“在计算机科学中，二分搜索是一种算法，用于通过检查中间、排除列表的一半，然后对剩余的一半执行搜索来定位排序列表中元素的位置。[1][2] ] 如果中间元素等于查找值，则该位置已经找到；否则，根据该元素是大于还是小于中间元素，选择上半部分或下半部分进行搜索。”

So the prerequisite for binary search is that the data is sorted. It has to be sorted because it cuts the array in half and looks at the middle element. If the middle element is what it is looking for it is done. If the middle element is larger it takes the lower half of the array. If the middle element is smaller it the upper half of the array. Then the process is repeated (look in the middle etc...) until the element is found (or not).

所以二分查找的前提是对数据进行排序。它必须排序，因为它将数组切成两半并查看中间元素。如果中间元素是它正在寻找的东西，它就完成了。如果中间元素较大，则占用数组的下半部分。如果中间元素较小，则为数组的上半部分。然后重复该过程（查看中间等...），直到找到（或未找到）元素。

If the data isn't sorted the algorithm cannot work.

如果数据未排序，则算法无法工作。

So you would do something like:

所以你会做这样的事情：

final String[] data;
final int      index;

data = new String[] { /* init the elements here or however you want to do it */ };
Collections.sort(data);
index = Arrays.binarySearch(data, value);

or, if you do not want to sort it do a linear search:

或者，如果您不想对其进行排序，请进行线性搜索：

int index = -1; // not found

for(int i = 0; i < data.length; i++)
{
    if(data[i].equals(value))
    {
        index = i;
        break; // stop looking
    }
}

And for completeness here are some variations with the full method:

为了完整起见，这里是完整方法的一些变体：

// strict one - disallow nulls for everything
public <T> static int linearSearch(final T[] data, final T value)
{
    int index;

    if(data == null)
    {
        throw new IllegalArgumentException("data cannot be null");
    }

    if(value == null)
    {
        throw new IllegalArgumentException("value cannot be null");
    }

    index = -1;

    for(int i = 0; i < data.length; i++)
    {
        if(data[i] == null)
        {
            throw new IllegalArgumentException("data[" + i + "] cannot be null");
        }

        if(data[i].equals(value))
        {
            index = i;
            break; // stop looking
        }
    }    

    return (index);
}

// allow null for everything

// 允许所有内容为 null

public static <T> int linearSearch(final T[] data, final T value)
{
    int index;

    index = -1;

    if(data != null)
    {
        for(int i = 0; i < data.length; i++)
        {
            if(value == null)
            {
                if(data[i] == null)
                {
                    index = i;
                    break;
                }
            } 
            else
            {            
                if(value.equals(data[i]))
                {
                    index = i;
                    break; // stop looking
                }
            }
        }    
    }

    return (index);
}

You can fill in the other variations, like not allowing a null data array, or not allowing null in the value, or not allowing null in the array. :-)

您可以填写其他变体，例如不允许空数据数组，或不允许值中为空，或不允许数组中为空。:-)

Based on the comments this is also the same as the permissive one, and since you are not writing most of the code it would be better than the version above. If you want it to be paranoid and not allow null for anything you are stuck with the paranoid version above (and this version is basically as fast as the other version since the overhead of the method call (asList) probably goes away at runtime).

根据评论，这也与宽容的相同，并且由于您没有编写大部分代码，因此它会比上面的版本更好。如果您希望它是偏执的并且不允许为任何内容使用 null，那么您会被上面的偏执版本卡住（并且此版本基本上与其他版本一样快，因为方法调用 (asList) 的开销可能会在运行时消失）。

public static <T> int linearSearch(final T[] data, final T value)
{
    final int index;

    if(data == null)
    {
        index = -1;
    }
    else
    {
        final List<T> list;

        list  = Arrays.asList(data);
        index = list.indexOf(value);
    }

    return (index);
}

回答by Mark Byers

java.util.Arrays.sort(myArray);

java.util.Arrays.sort(myArray);

That's how binarySearch is designed to work - it assumes sorting so that it can find faster.

这就是 binarySearch 的工作原理 - 它假设排序以便可以更快地找到。

If you just want to find something in a list in O(n) time, don't use BinarySearch, use indexOf. All other implementations of this algorithm posted on this page are wrong because they fail when the array contains nulls, or when the item is not present.

如果您只想在 O(n) 时间内在列表中查找某些内容，请不要使用 BinarySearch，请使用indexOf。此页面上发布的此算法的所有其他实现都是错误的，因为它们在数组包含空值或项目不存在时失败。

public static int indexOf(final Object[] array, final Object objectToFind, int startIndex) {
    if (array == null) {
        return -1;
    }
    if (startIndex < 0) {
        startIndex = 0;
    }
    if (objectToFind == null) {
        for (int i = startIndex; i < array.length; i++) {
            if (array[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = startIndex; i < array.length; i++) {
            if (objectToFind.equals(array[i])) {
                return i;
            }
        }
    }
    return -1;
}

回答by Michael Mao

Of all the overloaded versions of binarySearch in Java, there is no such a version which takes an argument of String. However, there are three types of binarySearch that might be helpful to your situation:

在 Java 中 binarySearch 的所有重载版本中，没有这样的版本接受 String 参数。但是，有三种类型的 binarySearch 可能对您的情况有所帮助：

static int binarySearch(char[] a, char key); static int binarySearch(Object[] a, Object key); static int binarySearch(T[] a, T key, Comparator c)

static int binarySearch(char[] a, char key); static int binarySearch(Object[] a, Object key); static int binarySearch(T[] a, T key, Comparator c)

回答by TofuBeer

To respond correctly to you question as you have put it. Use brute force

正确回答你提出的问题。使用蛮力

回答by Vaibhav

I hope it will help

我希望它会有所帮助

   public int find(String first[], int start, int end, String searchString){
    int mid = start + (end-start)/2;
    // start = 0;
    if(first[mid].compareTo(searchString)==0){
        return mid;
    }
    if(first[mid].compareTo(searchString)> 0){
        return find(first, start, mid-1, searchString);
    }else if(first[mid].compareTo(searchString)< 0){
        return find(first, mid+1, end, searchString);
    }
    return -1;
  }