Блог

#java #algorithm

#java #алгоритм

Вопрос:

 public class LocalMinimum {
/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    // TODO code application logic here
    int[] array = {8, 5, 7, 2, 3, 0, 1, 9};        
    int leftIndex = 0;
    int rightIndex = array.length -1;
    while (leftIndex < rightIndex) {
        int middleIndex = (leftIndex   rightIndex)/2;
        if ((array[middleIndex] < array[middleIndex - 1]) amp;amp; 
                (array[middleIndex] < (array[middleIndex   1]))) {
            System.out.println("Local minimum: "   array[middleIndex]);
            break;
        }
        else if (array[middleIndex - 1] < array[middleIndex   1]) {
            rightIndex = middleIndex - 1;
        }
        else {
            leftIndex = middleIndex   1;
        }
    }


    }
 }
  

Комментарии:

1. Вы пытаетесь получить минимальное значение в массиве?

2. Можете ли вы конкретно определить, что вы подразумеваете под «локальным минимумом»? Потому что, если это просто любое значение меньше, чем значение до и после него, ваша основная проблема заключается в том, что по какой-то причине вы создали монстра, похожего на Франкенштейна, необъяснимым образом объединив поиск локальных минимумов с бинарным поиском. Возможно, вы захотите начать все сначала, спланировав свою логику на бумаге, а затем реализовав ее.

3. Сейчас неподходящее время для использования двоичного поиска. Двоичный поиск предназначен для поиска значений в отсортированных массивах. Ваш массив не отсортирован — двоичный поиск не принесет вам никакой пользы.

4. извините, это должно быть в O (logn) временной сложности, и когда я говорю локальный минимум, это должно быть целое число, меньшее, чем значение справа и слева от него. Мне не нужно находить все локальные минимумы массива, поэтому я просто ищу половину массива

5. @NicholasWhitfield Какую половину вы ищете? Поиск половины массива будет O(n/2) which is O(n) , поэтому я не совсем уверен, что вы пытаетесь сделать.

Ответ №1:

 int[] array = {8, 5, 7, 2, 3, 0, 1, 9};

for (int i=0; i < array.length;   i) {
    if ( (i == 0 || array[i] < array[i-1]) amp;amp;
         (i == array.length-1 || array[i] < array[i 1])) {
        System.out.println("Local minimum: "   array[i]);
    }
}
  

Ответ №2:

 int[] array = {8, 5, 7, 2, 3, 0, 1, 9};

for (int index = 1; index < array.length - 1; index  )
{
    if (array[index] < array[index - 1] amp;amp;
        array[index] < array[index   1])
    {
        System.out.println("Local minimum: "   array[index]);
    }
}
  

Комментарии:

1. @Tim На самом деле мы не знаем, включает ли определение OPs конечные точки или нет. На мой взгляд, ваш ответ и этот — две разные допустимые интерпретации неясного вопроса. Хотя в примере массива это не имеет никакого значения.

2. это то, что я сделал сначала, но это должно быть в O (logn) время сложности

3. @NicholasWhitfield Пожалуйста, отредактируйте свой вопрос так, чтобы он объяснял, что вы пытаетесь сделать, и как вы хотите найти этот результат. Таким образом, я могу отредактировать свой ответ так, чтобы он соответствовал этому вопросу.

4. @NicholasWhitfield Вы уверены, что это ваше требование? Как поиск может занять меньше N шагов для завершения, предполагая, что каждый сегмент должен быть рассмотрен как кандидат на локальный минимум?

Ответ №3:

 for(int i=1;i<array.length;i  ) {
    if(array[i]<array[i-1] amp;amp; array[i]<array[i 1]) {
        System.out.println(array[i]);
    }
}