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

Question

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

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

其中键是String[]键,键是键String

我读了一些关于需要对数组进行排序的内容,但是如果是这样的话,我怎么做呢？

鉴于这一切,我真的需要知道:

如何在字符串数组(小于1000)中搜索字符串呢？

Answer 1

来自维基百科:

"在计算机科学中,二分搜索是一种算法,用于通过检查中间位置来定位元素在排序列表中的位置,从中考虑排除一半列表,然后对剩余的一半执行搜索.[1] [2 ]如果中间元素等于所寻找的值,则找到位置;否则,根据元素是否大于或小于中间元素,选择上半部分或下半部分进行搜索.

因此二进制搜索的先决条件是数据已排序.它必须进行排序,因为它将数组切成两半并查看中间元素.如果中间元素正在寻找它,那就完成了.如果中间元素较大,则需要数组的下半部分.如果中间元素较小,则为数组的上半部分.然后重复该过程(查看中间等...),直到找到(或不找到)元素.

如果数据未排序,则算法无法工作.

所以你会做类似的事情:

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);

或者,如果您不想对其进行排序,请执行线性搜索:

int index = -1; // not found

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

为了完整起见,这里有完整方法的一些变化:

// 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);
}

//允许所有内容为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);
}

您可以填写其他变体,例如不允许空数据数组,或者不允许在值中使用null,或者不允许在数组中使用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);
}

Answer 2

java.util.Arrays.sort(myArray);

这就是binarySearch的设计工作方式 - 它假定排序以便更快地找到它.

如果您只想在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;
}