Intereting Posts
Функция scanf, кажется, пропущена в c предупреждение: предлагать круглые скобки вокруг присваивания, используемые как значение истины Ошибка при декодировании AAC с помощью avcodec_decode_audio4 () LD_PRELOAD не работает с моей программой Как проверить, существует ли файл в c Этот код сборки ничего не делает Как быстро вы можете выполнять линейный поиск? Эффективное развертывание ручного цикла Является ли IEEE-754 поплавок, двойным и квадратным гарантией точного представления -2, -1, -0, 0, 1, 2? Разница между заголовком и контентом ответа HTTP-сервера (сокетов) Отдельные символы не печатаются на терминале C: указатель на массив указателей на структуры (проблемы выделения / освобождения) Обучение SIFT в OpenCV Не удалось реализовать функцию с переменными аргументами Portaudio не будет воспроизводить звук, если в настоящее время воспроизводится другая программа

Как я могу упростить этот рабочий двоичный код поиска в C?

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

bool search(int value, int values[], int n) { int min = values[0]; int max = values[n-1]; int average = (min + max) / 2; if(average == value) { return true; } while (average > value) { max = average - 1; average = (min + max) / 2; } while (average < value) { min = average + 1; average = (min + max) / 2; } if (max < min) { return false; } if (average == value) { printf("%i\n", average); return true; } else { return false; } } 

Это не правильная реализация двоичного поиска, все условия должны быть в одном цикле, например: Также max должен быть n-1, а не значениями [n-1] и min = 0 вместо значений [0], а также вы должны сравнить значения [средний] со значением не только средней переменной.

  bool search(int value, int values[], int n){ int min = 0; int max = n-1; int average ; while(max>=min){ average = (min + max) / 2; if(values[average] == value) { return true; } if (values[average] > value) { max = average - 1; average = (min + max) / 2; } if (values[average] < value) { min = average + 1; average = (min + max) / 2; } } return false; } в  bool search(int value, int values[], int n){ int min = 0; int max = n-1; int average ; while(max>=min){ average = (min + max) / 2; if(values[average] == value) { return true; } if (values[average] > value) { max = average - 1; average = (min + max) / 2; } if (values[average] < value) { min = average + 1; average = (min + max) / 2; } } return false; } 

В бинарном поиске есть множество мелочей: обработайте случай length = 0, убедитесь, что проверяемая вами позиция всегда действительна, убедитесь, что вы не переполняете (например, `(low + high) / 2 ‘не лучший способ написать это), убедитесь, что новая тестовая позиция всегда отличается от предыдущей и т. Д.

Сделав это как миллион раз, каждый бинарный поиск, который я пишу, теперь выполняется следующим образом:

 bool search(int[] array, int length, int valueToFind) { int pos=0; int limit=length; while(pos>1); if (array[testpos] в bool search(int[] array, int length, int valueToFind) { int pos=0; int limit=length; while(pos>1); if (array[testpos] 

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

То, как мы вычисляем testpos гарантирует, что pos <= testpos < limit , AND работает, даже если длина является наибольшим возможным целочисленным значением.

Эта форма также позволяет легко считывать инварианты, которые вы хотите видеть, не задумываясь о странных граничных условиях, таких как high . Когда вы выходите из цикла, pos==limit поэтому вам не нужно беспокоиться об использовании неправильного и т. Д.

Условие в этом цикле также легко адаптируется к бинарным поискам различного назначения, таким как «найти, куда вставлять x, гарантируя, что он идет после всех xs, которые уже находятся в массиве», «найти первый x в массиве», найти последний x в массиве "и т. д.