Алгоритм первого позиционирования Java

ProgramBox

Алгоритм первого позиционирования Java

Post author:admin
Запись опубликована:21 апреля, 2023
Post category:Вопросы по программированию

#java #arrays #algorithm #binary-search

#java #массивы #алгоритм #двоичный поиск

Вопрос:

 int firstPosition(int x, int [] a) {

    int lower = 0;
    int upper = a.length;

    while (lower != upper) {
    int mid = (lower   upper) / 2;

    **if (x <= a[mid]) {** // the line I don't understand
    upper = mid;
    } else {
    lower = mid   1;
    }
    return (lower);
}

Если = {4, 4, 5, 5, 6, 7, 8, 9, 9, 9} что алгоритм вернет для следующих вариантов x?

i) x = 3

ii) x = 4

iii) x = 5

iv) x = 9

v) x = 11

Я попытался пошагово выполнить эту программу, например, x = 3, a.длина возвращает 10, поэтому значение upper всегда равно 10.

 while ( 3 ! = 0 ) { // execute line

int mid = lower   upper / 2 - which is (0   10)/2 = 5

if ( x <= a[mid]) // I assume that means if 3 is less than or equal to 5? 5 then replace mid with 5 and then...

lower = mid   1 // 5 1 = 6, return 6 as lower?

Ответ №1:

Это базовый алгоритм бинарного поиска, реализованный итеративно, а не рекурсивно.

Строка, которую вы не понимаете, проверяет, x (значение поиска) может находиться в нижней или верхней половине массива. Это работает, потому что массив отсортирован. Мы можем разделить любой отсортированный массив на две половины и посмотреть на значение в середине, чтобы определить, в какой половине может находиться искомое значение.

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

  --- --- --- --- --- ---- 
| 1 | 3 | 5 | 7 | 9 | 11 |
 --- --- --- --- --- ---- 
  ^                        ^
  |                        |
lower                    upper

и мы пытаемся выяснить, в каком слоте находится число 9 . Поскольку массив отсортирован, мы можем немедленно отбросить половину массива.

Как?

Посмотрите на значение в «центре» массива: оно 5 , и 9 больше, чем 5 , поэтому мы знаем, что 9 оно должно быть в верхней половине массива.Говоря алгоритмически, это было бы else случаем if инструкции в вашем коде.

Итак, мы повторяем тот же процесс, но на этот раз смотрим только на верхнюю половину массива:

  --- --- --- --- --- ---- 
| 1 | 3 | 5 | 7 | 9 | 11 |
 --- --- --- --- --- ---- 
              ^            ^
              |            |
            lower        upper

Ответ №2:

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

1. Итак, если x = 3, возвращает ли lower значение 6?

2. lower это переменная, а не функция / метод, поэтому она ничего не «возвращает»,

3. Да, поскольку длина массива равна 10, поэтому mid равно 5. Поскольку 3 < 5, lower становится mid 1 . Таким образом lower становится 6

4. Сколько раз выполняется тело цикла в зависимости от длины массива?

5. Теперь звучит как домашнее задание. @Paradox: Что вы заметили о размере «массива» (т. Е. о том, что происходит с upper - lower приблизительно) на каждой итерации цикла? Это должно дать вам подсказку.

Ответ №3:

Это модификация двоичного поиска.

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

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