Реализация бинарного поиска по массиву строк

Question

У меня есть проблемы с этим. Массив ввода основан на вводе файла, а размер массива определяется первой строкой в ​​файле. Метод binarySearch выглядит хорошо, но, похоже, не работает. Кто-нибудь сможет помочь? Благодарю.

public static int binarySearch(String[] a, String x) {
    int low = 0;
    int high = a.length - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;

        if (a[mid].compareTo(x) < 0) {
            low = mid + 1;
        } else if (a[mid].compareTo(x) > 0) {
            high = mid - 1;
        } else {
            return mid;
        }
    }

    return -1;
}

public static void main(String[] args) {

    Scanner input = new Scanner(System.in);

    System.out.println("Enter the name of your file (including file extension): ");
    String filename = input.next();

    String[] numArray;
    try (Scanner in = new Scanner(new File(filename))) {
        int count = in.nextInt();

        numArray = new String[count];

        for (int i = 0; in.hasNextInt() && count != -1 && i < count; i++) {
            numArray[i] = in.nextLine();
        }

        for (int i = 0; i < count; i++) //printing all the elements
        {
            System.out.println(numArray[i]);
        }

        String searchItem = "The";

        System.out.println("The position of the String is:");
        binarySearch(numArray, searchItem);

    } catch (final FileNotFoundException e) {
        System.out.println("That file was not found. Program terminating...");
        e.printStackTrace();

    }

}

Answer 1

Я добавил следующий пример для вашего дальнейшего использования.

import java.util.Arrays;

public class BinaryStringSearch {

    public static void main(String[] args) {

        String array[] ={"EWRSFSFSFSB","BB","AA","SDFSFJ","WRTG","FF","ERF","FED","TGH"};
        String search = "BB";

        Arrays.sort(array);

        int searchIndex = binarySearch(array,search);

        System.out.println(searchIndex != -1 ? array[searchIndex]+ " - Index is "+searchIndex : "Not found");
    }

    public static int binarySearch(String[] a, String x) {
        int low = 0;
        int high = a.length - 1;
        int mid;

        while (low <= high) {
            mid = (low + high) / 2;

            if (a[mid].compareTo(x) < 0) {
                low = mid + 1;
            } else if (a[mid].compareTo(x) > 0) {
                high = mid - 1;
            } else {
                return mid;
            }
        }

        return -1;
    }

}

Answer 2

Надеюсь, это поможет:

 public static void main(String ar[]){

    String str[] = {"account","angel","apple","application","black"};
    String search= "application";
    int length = str.length-1;
    BinarySearchInString findStrin = new BinarySearchInString();
    int i = findStrin.find(str, 0, length, search);
    System.out.println(i);
}

  public int find(String first[], int start, int end, String searchString){
    int mid = start + (end-start)/2;

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

Answer 3

Как заметил @Mike Rylander, вы забыли вывести результат.

Вы должны использовать Arrays.binarySearch вместо вашей собственной реализации.

(Как правило, библиотеки JRE хорошо протестированы, хорошо документированы и быстры. Я гуглил "бинарный поиск Java", и этот вопрос хорошо ранжирован. Я попытался с кодом @Thusitha Indunil, который, похоже, не работать. Я погуглил и нашел Arrays.binarySearch, который работал.)

Answer 4

Я считаю, что ваша проблема в том, что вы забыли вывести результаты. Попробуйте заменить binarySearch(numArray, searchItem); с System.out.println(binarySearch(numArray, searchItem));

Answer 5

          int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;

        Comparable midVal = (Comparable) a[mid];

        int cmp = midVal.compareTo(key);

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid;
    }
    return -(low + 1);
}

Answer 6

Есть четыре проблемы, которые я могу заметить в дополнение к уже упомянутому отсутствующему отпечатку результата.

1: у вас есть String[] называется numArray и вы ищете String, "The" имя numArray возможно, немного ошибочен.

2: я предполагаю, что у вас есть какой-то определенный формат входного файла, где число String в файле указаны integer как первый токен в файле. Это нормально, однако, как условие в цикле for, который заполняет numArray есть in.hasNextInt()и следующий токен извлекается из Scanner с помощью in.nextLine(), Вы должны использовать дополнительные методы проверки / удаления, такие как in.hasNext() с in.next(), Проверьте Scanner API.

3: binarySearch(String[], String) метод использует String.compareTo(String), Это определяет лексикографическое упорядочение этого String к параметру String, Попытка сравнить верхний регистр с нижним регистром может не дать ожидаемого результата, так как "the".compareTo("The") не приведет к 0, Вы должны проверить String API для параметров, чтобы либо принудительно вводить все ваши данные в одном случае, возможно, при чтении файла, либо использовать другой вариант сравнения с методом.

4: последнее, что я вижу, может считаться чем-то вроде углового случая, однако с достаточно большим String массив, и строка поиска, которая может находиться далеко в правой части, т.е. сторона высокого индекса, из массива вы можете получить ArrayIndexOutOfBoundsException, Это потому что (low + high) может привести к отрицательному значению, когда результат "должен" быть больше, чем Integer.MAX_VALUE, Затем результат делится на два и все равно дает отрицательное значение. Это может быть решено путем сдвига битов результата вместо деления на 2, (low + high) >>> 1, У Джошуа Блоха есть отличная статья об этом распространенном недостатке в алгоритмах разделяй и властвуй.