Двоичный поиск работает для целочисленных массивов, но не для двойных массивов - PullRequest
Новая
       18

Двоичный поиск работает для целочисленных массивов, но не для двойных массивов

0 голосов
/ 25 апреля 2020

Я работаю над одним из примеров из вступления к Java учебнику 10-го издания Даниэля Ляна. Я столкнулся с проблемой в главе 7 при выполнении двоичного поиска в одномерном массиве. Мой код работает нормально, когда я использую его на целочисленном массиве, но он не работает, когда я вводю double.

обновление: 25/4/2020 13:20 по восточному времени США

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

static boolean equals(double a, double b){
        if (Math.abs(a - b) <= epsilon) return true;
        return false;

и затем вызвав его в методе двоичного поиска следующим образом: 

while(high>=low){
            int mid = (int) ((low+high)/2);
            if (key < a[mid])
                high = mid - 1;
            else if (equals(key, a[mid]))
                return mid;
            else
                low= mid + 1;

Я не уверен, что проблема теряет точность, потому что хотя я Я использую двойники, они все целые числа. Ниже приведен исходный код подписи метода учебника, измененный для отражения двойного. 

class Scratch {

//I created two class array variables here to test the binary search approach. 

static double[] myList = {12.0,34.0,5.0,6.0,78.0,89.0,0.0};
static int[] a = {5,1,3,3,4};

//Main method call 
public static void main(String[] args) {
      System.out.println(binarySearch(myList, 12.0));


    }
public static int binarySearch(double[] a, double key){
        int low = 0;
        int high = a.length-1;
        while(high>=low){
            int mid = (int) ((low+high)/2);
            if (key < a[mid])
                high = mid - 1;
            else if (key == a[mid])
                return mid;
            else
                low= mid + 1;
        }
        return -low -1;
    }

Компьютер печатает отрицательное число, сигнализирующее, что ключ не был найден.

Спасибо!

Ответы [ 3 ]

1 голос
/ 25 апреля 2020

Как уже упоминалось, тип double имеет точность limit .

Что вы можете сделать, это изменить эту строку else if (key == a[mid]).

И вместо строгого ==, вы можете попытаться ввести "достаточно хорошие" критерии. например, 

// it can really be any number. depending on how "precise" you want
static double epsilon = 1e-9; 
static boolean equals(double a, double b) {
    if (Math.abs(a-b) <= epsilon) return true; 
    return false; 
}
... 
...
else if (equals(key, a[mid])) return mid; 
...

РЕДАКТИРОВАТЬ: Чтобы алгоритм двоичного поиска работал, массив должен быть SORTED . Ключевая идея бинарного поиска Разделяй и властвуй .

Идея, лежащая в основе этого, довольно проста: для большой проблемы, если мы сможем уменьшить сложность ее решения, тогда она станет меньшей проблемой. (шаг 1) Если каким-то образом мы можем свести меньшую проблему к еще меньшей проблеме (возможно, повторно применив метод на шаге 1), это еще на один шаг ближе к поиску решения (шаг 2). На каждом шаге мы все ближе и ближе, пока проблема не станет настолько тривиальной для решения.

Рекомендую посмотреть несколько хороших видео онлайн, например, этот один

0 голосов
/ 25 апреля 2020

Вы не дали нам достаточно информации, чтобы точно знать как у вас возникли проблемы, но я собираюсь догадаться, что вы сделали что-то вроде этого: 

double[] a = ...     // create and initialize
int i = ...          // a valid subscript for 
int result = binarySearch(a, (int)(a[i])); 
                     // result is -1

Вот почему это не работает

  • Когда вы приводите значение с плавающей запятой к целочисленному типу, вы можете потерять точность; то есть 1.5 становится 1, и вы потеряли 0.5.
  • Когда вы сравниваете тип с плавающей запятой и целочисленный тип, используя ==, <, > и т. д., интегральное значение преобразуется в ближайшее значение в типе с плавающей запятой ... перед сравнением чисел. Это преобразование также может потерять точность.

Итак, когда мы посмотрим, что делает ваш код, вы возьмете double в вашем массиве a, приведя его к int так что вы можете использовать его как key ... и затем преобразовывать key обратно в double каждый раз, когда binarySearch выполняет сравнение. 

double -> int -> double.

Причина, по которой вы видите глюки, заключается в том, что что начальный double и конечный double не совпадают с a[i], который вы ищете. Так что == дает вам false, когда вы хотите, чтобы оно было true.

Решение состоит в том, чтобы изменить тип key, чтобы он совпадал с базовым типом массива, который вы используете. в поиске. Так что нет необходимости приводить или преобразовывать значения.

Улилоп поднимает еще один важный момент в своем ответе. Даже если мы исключим преобразования, которые я описал выше, компьютерные числа с плавающей запятой и арифметически с плавающей запятой принципиально неточны. Например: 

double one_third = 1.0 / 3.0;
double one = one_third * 3.0;
System.printf(one == 1.0);       // prints "false" !!!!

Поэтому, когда вы делаете что-либо, связанное со сравнением значений с плавающей запятой, вы должны учитывать возможность округления ошибок в вычислениях.

Подробнее об этом topi c, прочитайте их:

НАКОНЕЦ вы предоставили нам свой реальный код.

Причина, по которой ваш реальный код дает вам неправильный ответ, заключается в том, что что вы выполняете двоичный поиск в массиве, который не упорядочен. Бинарный поиск работает только в том случае, если искомый массив упорядочен. Как Википедия заявляет:

"В информатике бинарный поиск, также известный как полуинтервальный поиск, логарифмический поиск c или бинарная отбивная, является Алгоритм поиска, который находит позицию целевого значения в отсортированном массиве . "

0 голосов
/ 25 апреля 2020

Является ли удвоение точным числом?

Когда вы сравниваете двойные и целые числа, изменение десятичного значения сделает оператор сравнения ложным.

Обходной путь может быть приведен к двойному int при сравнении. 

public class Main {
    public static void main(String[] args) throws Exception {
        double d1 = 100.000000001;
        double d2 = 100.000000000;
        int i = 100;

        System.out.println(d1 == i);
        System.out.println(d2 == i);
        int int1 = (int)d1;
        int int2 = (int)d2;

        System.out.println(int1 == i);
        System.out.println(int2 == i);
    }
}

Вывод: 

false
true
true
true
...