Элегантный способ найти два последовательных значения в отсортированном массиве, которые связывают данное значение?

Question

У меня есть массив отсортированных целых чисел, и я хотел бы получить два последовательных индекса элементов, которые связывают конкретное значение, которое я передаю. Чтобы проиллюстрировать это, потому что это трудно описать словами, скажем, у меня есть массив(обычный индекс с нулевым индексом):

1 3 4 5 7 9

Я хочу получить два индекса, которые ограничивают, скажем, значение 6. В этом случае массив имеет значения 5 и 7 в последовательных позициях, которые ограничиваютзначение, которое я ищу (5 <= 6 <= 7), и поэтому я бы вернул индекс 5 и индекс 7 (3 и 4 соответственно). </p>

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

Есть ли элегантный способ сделать это?На какие угловые случаи мне следует обратить внимание, и как я могу с ними справиться и / или проверить?Спасибо!

Answer 1

Вы можете решить проблему с помощью бинарного поиска или решить ее в O (lg (n)), не рассматривая так много граничных случаев. Идея состоит в том, чтобы использовать бинарный поиск, чтобы найти самый низкий элемент, больший или равный значению привязки (назовем его x).

pair<int, int> FindInterval(const vector<int>& v, int x) {
  int low = 0, high = (int)v.size();
  while (low < high) {
    const int mid = (low + high) / 2;
    if (v[mid] < x) low = mid + 1;
    else high = mid;
  }
  // This if is used to detect then a bound (a <= x <= x) is impossible but a
  // bound (x <= x <= can be found).
  if (low == 0 && low < (int)v.size() && v[low] == x) ++low;
  return make_pair(low - 1, low);
}

Обратите внимание, что ответом может быть (-1, 0), что означает отсутствие нижней границы для интервала, это может быть (n - 1, n), что означает отсутствие верхней границы для интервала (где n - это размер v). Кроме того, возможны два возможных ответа, если x находится в v, и может быть несколько ответов, если x многократно в v, потому что границы включают крайние значения.

Наконец, вы можете заменить двоичный поиск функцией std::lower_bound:

pair<int, int> FindInterval(const vector<int>& v, int x) {
  // This does the same as the previous hand-coded binary search.
  const int low = (int)(lower_bound(v.begin(), v.end(), x) - v.begin());

  // The rest of the code is the same...
}

Answer 2

В основном:

1. Сортировать массив ( один раз );
2. Выполните поиск пополам, чтобы найти ближайший элемент;
3. Сравните этот элемент с входным значением;
   • Если она ниже, у вас есть нижняя граница;
   • Если оно выше, у вас есть более высокая граница;
   • Если это то же самое, то границы находятся рядом с элементом.

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

В конечном счете, это немного больше, чем поиск по разделениям в отсортированном массиве, поэтому O (log n) в отсортированном массиве и O (n log n) в несортированном массиве.

Answer 3

Двоичный поиск нужного значения (в данном случае 6).

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

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

Answer 4

Один из способов сделать это быстрее - использовать бинарный поиск .Это уменьшит сложность текущего времени с O (n) до O (log n) .